# Reduce sum of same-indexed elements of two arrays to less than K by rearranging the second array

Given two arrays **arr1[]** and **arr2[]**, both of size **N** and an integer **X**, the task is to check if the sum of same-indexed elements of both the arrays at corresponding indices can be made **at most K** after rearranging the second array. If it is possible then print **“Yes”** else print **“No”**.

**Examples:**

Input:arr1[] = {1, 2, 3}, arr2[] = {1, 1, 2}, X = 4Output:YesExplanation:

Rearranging the array B[] as {1, 2, 1}. Now the sum of corresponding indices are:

A[0] + B[0] = 1 + 1 = 2 ≤ 4

A[1] + B[1] = 2 + 2 = 4 ≤ 4

A[2] + B[2] = 3 + 1 = 4 ≤ 4

Input:arr1[] = {1, 2, 3, 4}, arr2[] = {1, 2, 3, 4}, X = 4Output:NoExplanation:There is no way that the array B[] can be rearranged such that the condition A[i] + B[i] <= X is satisfied.

**Naive Approach:** The simplest approach is to generate all possible permutations of the array **B[]** and if any permutation satisfies the given condition, then print **Yes**. Otherwise, print **No**.

**Time Complexity:** O(N!)**Auxiliary Space:** O(1)

**Efficient Approach:** To optimize the above approach, the idea is to use Sorting. Follow the steps below to solve the problem:

- Sort the array
**arr1[]**in ascending order and**arr2[]**in descending order. - Now, traverse both the arrays simultaneously and if there exists any pair such that the sum of
**arr1[i]**and**arr2[]**exceeds**X**, then print**“No”**. Otherwise, print**“Yes”**.

Below is the implementation of the above approach:

## C++

`// C++ program for the above approach` `#include <bits/stdc++.h>` `using` `namespace` `std;` `// Function to check if elements` `// of B[] can be rearranged` `// such that A[i] + B[i] <= X` `void` `rearrange(` `int` `A[], ` `int` `B[],` ` ` `int` `N, ` `int` `X)` `{` ` ` `// Checks the given condition` ` ` `bool` `flag = ` `true` `;` ` ` `// Sort A[] in ascending order` ` ` `sort(A, A + N);` ` ` `// Sort B[] in descending order` ` ` `sort(B, B + N, greater<` `int` `>());` ` ` `// Traverse the arrays A[] and B[]` ` ` `for` `(` `int` `i = 0; i < N; i++) {` ` ` `// If A[i] + B[i] exceeds X` ` ` `if` `(A[i] + B[i] > X) {` ` ` `// Rearrangement not possible,` ` ` `// set flag to false` ` ` `flag = ` `false` `;` ` ` `break` `;` ` ` `}` ` ` `}` ` ` `// If flag is true` ` ` `if` `(flag)` ` ` `cout << ` `"Yes"` `;` ` ` `// Otherwise` ` ` `else` ` ` `cout << ` `"No"` `;` `}` `// Driver Code` `int` `main()` `{` ` ` `int` `A[] = { 1, 2, 3 };` ` ` `int` `B[] = { 1, 1, 2 };` ` ` `int` `X = 4;` ` ` `int` `N = ` `sizeof` `(A) / ` `sizeof` `(A[0]);` ` ` `// Function Call` ` ` `rearrange(A, B, N, X);` ` ` `return` `0;` `}` |

## Java

`// Java program for the above approach` `import` `java.util.*;` `class` `GFG` `{` ` ` `// Function to check if elements` ` ` `// of B[] can be rearranged` ` ` `// such that A[i] + B[i] <= X` ` ` `static` `void` `rearrange(` `int` `A[], ` `int` `B[],` ` ` `int` `N, ` `int` `X)` ` ` `{` ` ` `// Checks the given condition` ` ` `boolean` `flag = ` `true` `;` ` ` `// Sort A[] in ascending order` ` ` `Arrays.sort(A);` ` ` `// Sort B[] in descending order` ` ` `Arrays.sort(B);` ` ` `// Traverse the arrays A[] and B[]` ` ` `for` `(` `int` `i = ` `0` `; i < N; i++)` ` ` `{` ` ` `// If A[i] + B[i] exceeds X` ` ` `if` `(A[i] + B[N - ` `1` `- i] > X)` ` ` `{` ` ` `// Rearrangement not possible,` ` ` `// set flag to false` ` ` `flag = ` `false` `;` ` ` `break` `;` ` ` `}` ` ` `}` ` ` `// If flag is true` ` ` `if` `(flag == ` `true` `)` ` ` `System.out.print(` `"Yes"` `);` ` ` `// Otherwise` ` ` `else` ` ` `System.out.print(` `"No"` `);` ` ` `}` ` ` `// Driver Code` ` ` `public` `static` `void` `main (String[] args)` ` ` `{` ` ` `int` `A[] = { ` `1` `, ` `2` `, ` `3` `};` ` ` `int` `B[] = { ` `1` `, ` `1` `, ` `2` `};` ` ` `int` `X = ` `4` `;` ` ` `int` `N = A.length;` ` ` `// Function Call` ` ` `rearrange(A, B, N, X);` ` ` `}` `}` `// This code is contributed by AnkThon` |

## Python3

`# Python3 program for the above approach` `# Function to check if elements` `# of B can be rearranged` `# such that A[i] + B[i] <= X` `def` `rearrange(A, B, N, X):` ` ` ` ` `# Checks the given condition` ` ` `flag ` `=` `True` ` ` `# Sort A in ascending order` ` ` `A ` `=` `sorted` `(A)` ` ` `# Sort B in descending order` ` ` `B ` `=` `sorted` `(B)[::` `-` `1` `]` ` ` `# Traverse the arrays A and B` ` ` `for` `i ` `in` `range` `(N):` ` ` `# If A[i] + B[i] exceeds X` ` ` `if` `(A[i] ` `+` `B[i] > X):` ` ` `# Rearrangement not possible,` ` ` `# set flag to false` ` ` `flag ` `=` `False` ` ` `break` ` ` `# If flag is true` ` ` `if` `(flag):` ` ` `print` `(` `"Yes"` `)` ` ` `# Otherwise` ` ` `else` `:` ` ` `print` `(` `"No"` `)` `# Driver Code` `if` `__name__ ` `=` `=` `'__main__'` `:` ` ` `A ` `=` `[ ` `1` `, ` `2` `, ` `3` `]` ` ` `B ` `=` `[ ` `1` `, ` `1` `, ` `2` `]` ` ` `X ` `=` `4` ` ` `N ` `=` `len` `(A)` ` ` `# Function Call` ` ` `rearrange(A, B, N, X)` `# This code is contributed by mohit kumar 29` |

## C#

`// C# program for the above approach` `using` `System;` `using` `System.Collections.Generic;` `class` `GFG` `{` ` ` `// Function to check if elements` ` ` `// of B[] can be rearranged` ` ` `// such that A[i] + B[i] <= X` ` ` `static` `void` `rearrange(` `int` `[] A, ` `int` `[] B,` ` ` `int` `N, ` `int` `X)` ` ` `{` ` ` `// Checks the given condition` ` ` `bool` `flag = ` `true` `;` ` ` `// Sort A[] in ascending order` ` ` `Array.Sort(A);` ` ` `// Sort B[] in descending order` ` ` `Array.Sort(B);` ` ` `// Traverse the arrays A[] and B[]` ` ` `for` `(` `int` `i = 0; i < N; i++)` ` ` `{` ` ` `// If A[i] + B[i] exceeds X` ` ` `if` `(A[i] + B[N - 1 - i] > X)` ` ` `{` ` ` `// Rearrangement not possible,` ` ` `// set flag to false` ` ` `flag = ` `false` `;` ` ` `break` `;` ` ` `}` ` ` `}` ` ` `// If flag is true` ` ` `if` `(flag == ` `true` `)` ` ` `Console.WriteLine(` `"Yes"` `);` ` ` `// Otherwise` ` ` `else` ` ` `Console.WriteLine(` `"No"` `);` ` ` `}` ` ` `// Driver Code` ` ` `public` `static` `void` `Main()` ` ` `{` ` ` `int` `[]A = { 1, 2, 3 };` ` ` `int` `[]B = { 1, 1, 2 };` ` ` `int` `X = 4;` ` ` `int` `N = A.Length;` ` ` `// Function Call` ` ` `rearrange(A, B, N, X);` ` ` `}` `}` `// This code is contributed by AnkThon` |

## Javascript

`<script>` `// Javascript program of the above approach` `// Function to check if elements` `// of B[] can be rearranged` `// such that A[i] + B[i] <= X` `function` `rearrange(A, B, N, X)` `{` ` ` `// Checks the given condition` ` ` `let flag = ` `true` `;` ` ` ` ` `// Sort A[] in ascending order` ` ` `A.sort();` ` ` ` ` `// Sort B[] in descending order` ` ` `B.sort();` ` ` ` ` `// Traverse the arrays A[] and B[]` ` ` `for` `(let i = 0; i < N; i++)` ` ` `{` ` ` ` ` `// If A[i] + B[i] exceeds X` ` ` `if` `(A[i] + B[N - 1 - i] > X)` ` ` `{` ` ` ` ` `// Rearrangement not possible,` ` ` `// set flag to false` ` ` `flag = ` `false` `;` ` ` `break` `;` ` ` `}` ` ` `}` ` ` ` ` `// If flag is true` ` ` `if` `(flag == ` `true` `)` ` ` `document.write(` `"Yes"` `);` ` ` ` ` `// Otherwise` ` ` `else` ` ` `document.write(` `"No"` `);` `}` `// Driver Code` `let A = [ 1, 2, 3 ];` `let B = [ 1, 1, 2 ];` `let X = 4;` `let N = A.length;` `// Function Call` `rearrange(A, B, N, X);` `// This code is contributed by avijitmondal1998` `</script>` |

**Output:**

Yes

**Time Complexity:** O(N*log N)**Auxiliary Space:** O(1)

Attention reader! Don’t stop learning now. Get hold of all the important DSA concepts with the **DSA Self Paced Course** at a student-friendly price and become industry ready. To complete your preparation from learning a language to DS Algo and many more, please refer **Complete Interview Preparation Course****.**

In case you wish to attend **live classes **with experts, please refer **DSA Live Classes for Working Professionals **and **Competitive Programming Live for Students**.