# Permute two arrays such that sum of every pair is greater or equal to K

Given two arrays of equal size n and an integer k. The task is to permute both arrays such that sum of their corresponding element is greater than or equal to k i.e a[i] + b[i] >= k. The task is print “Yes” if any such permutation exists, otherwise print “No”.

Examples :

```Input : a[] = {2, 1, 3},
b[] = { 7, 8, 9 },
k = 10.
Output : Yes
Permutation  a[] = { 1, 2, 3 } and b[] = { 9, 8, 7 }
satisfied the condition a[i] + b[i] >= K.

Input : a[] = {1, 2, 2, 1},
b[] = { 3, 3, 3, 4 },
k = 5.
Output : No
```

The idea is to sort one array in ascending order and another array in descending order and if any index does not satisfy the condition a[i] + b[i] >= K then print “No”, else print “Yes”.

If the condition fails on sorted arrays, then there exists no permutation of arrays which can satisfy the inequality. Proof,

Assume asort[] be sorted a[] in ascending order and bsort[] be sorted b[] in descending order.
Let new permutation b[] is created by swapping any two indices i, j of bsort[],

• Case 1: i < j and element at b[i] is now bsort[j].
Now, asort[i] + bsort[j] < K, because bsort[i] > bsort[j] as b[] is sorted in decreasing order and we know asort[i] + bsort[i] < k.
• Case 2: i > j and element at b[i] is now bsort[j].
Now, asort[j] + bsort[i] < k, because asort[i] > asort[j] as a[] is sorted in increasing order and we know asort[i] + bsort[i] < k.

Below is the implementation is this approach:

div class="responsive-tabs">

## C++

 `// C++ program to check whether permutation of two ` `// arrays satisfy the condition a[i] + b[i] >= k. ` `#include ` `using` `namespace` `std; ` ` `  `// Check wheather any permutation exists which ` `// satisfy the condition. ` `bool` `isPossible(``int` `a[], ``int` `b[], ``int` `n, ``int` `k) ` `{ ` `    ``// Sort the array a[] in decreasing order. ` `    ``sort(a, a + n); ` ` `  `    ``// Sort the array b[] in increasing order. ` `    ``sort(b, b + n, greater<``int``>()); ` ` `  `    ``// Checking condition on each index. ` `    ``for` `(``int` `i = 0; i < n; i++) ` `        ``if` `(a[i] + b[i] < k) ` `            ``return` `false``; ` ` `  `    ``return` `true``; ` `} ` ` `  `// Driven Program ` `int` `main() ` `{ ` `    ``int` `a[] = { 2, 1, 3 }; ` `    ``int` `b[] = { 7, 8, 9 }; ` `    ``int` `k = 10; ` `    ``int` `n = ``sizeof``(a)/``sizeof``(a); ` ` `  `    ``isPossible(a, b, n, k) ? cout << ``"Yes"` `: ` `                             ``cout << ``"No"``; ` `    ``return` `0; ` `} `

## Java

 `// Java program to check whether  ` `// permutation of two arrays satisfy ` `// the condition a[i] + b[i] >= k. ` `import` `java.util.*; ` ` `  `class` `GFG  ` `{ ` `// Check wheather any permutation  ` `// exists which satisfy the condition. ` `static` `boolean` `isPossible(Integer a[], ``int` `b[], ` `                                  ``int` `n, ``int` `k)  ` `{ ` `    ``// Sort the array a[] in decreasing order. ` `    ``Arrays.sort(a, Collections.reverseOrder()); ` ` `  `    ``// Sort the array b[] in increasing order. ` `    ``Arrays.sort(b); ` ` `  `    ``// Checking condition on each index. ` `    ``for` `(``int` `i = ``0``; i < n; i++) ` `    ``if` `(a[i] + b[i] < k) ` `        ``return` `false``; ` ` `  `    ``return` `true``; ` `} ` ` `  `// Driver code ` `public` `static` `void` `main(String[] args) { ` `    ``Integer a[] = {``2``, ``1``, ``3``}; ` `    ``int` `b[] = {``7``, ``8``, ``9``}; ` `    ``int` `k = ``10``; ` `    ``int` `n = a.length; ` ` `  `    ``if` `(isPossible(a, b, n, k)) ` `    ``System.out.print(``"Yes"``); ` `    ``else` `    ``System.out.print(``"No"``); ` `} ` `} ` ` `  `// This code is contributed by Anant Agarwal. `

## Python3

 `# Python program to check ` `# whether permutation of two ` `# arrays satisfy the condition ` `# a[i] + b[i] >= k. ` ` `  `# Check whether any ` `# permutation exists which ` `# satisfy the condition. ` `def` `isPossible(a,b,n,k): ` ` `  `    ``# Sort the array a[] ` `    ``# in decreasing order. ` `    ``a.sort(reverse``=``True``) ` `  `  `    ``# Sort the array b[] ` `    ``# in increasing order. ` `    ``b.sort() ` `  `  `    ``# Checking condition ` `    ``# on each index. ` `    ``for` `i ``in` `range``(n): ` `        ``if` `(a[i] ``+` `b[i] < k): ` `            ``return` `False` `  `  `    ``return` `True` ` `  ` `  `# Driver code ` ` `  `a ``=` `[ ``2``, ``1``, ``3``] ` `b ``=` `[``7``, ``8``, ``9``] ` `k ``=` `10` `n ``=``len``(a) ` `  `  `if``(isPossible(a, b, n, k)): ` `    ``print``(``"Yes"``) ` `else``: ` `    ``print``(``"No"``) ` ` `  `# This code is contributed ` `# by Anant Agarwal. `

## C#

 `// C# program to check whether  ` `// permutation of two arrays satisfy ` `// the condition a[i] + b[i] >= k. ` `using` `System; ` ` `  `class` `GFG  ` `{ ` `// Check wheather any permutation  ` `// exists which satisfy the condition. ` `static` `bool` `isPossible(``int` `[]a, ``int` `[]b, ` `                       ``int` `n, ``int` `k)  ` `{ ` `    ``// Sort the array a[]  ` `    ``// in decreasing order. ` `    ``Array.Sort(a); ` ` `  `    ``// Sort the array b[]  ` `    ``// in increasing order. ` `    ``Array.Reverse(b); ` ` `  `    ``// Checking condition on each index. ` `    ``for` `(``int` `i = 0; i < n; i++) ` `    ``if` `(a[i] + b[i] < k) ` `        ``return` `false``; ` ` `  `    ``return` `true``; ` `} ` ` `  `// Driver code ` `public` `static` `void` `Main()  ` `{ ` `    ``int` `[]a = {2, 1, 3}; ` `    ``int` `[]b = {7, 8, 9}; ` `    ``int` `k = 10; ` `    ``int` `n = a.Length; ` ` `  `    ``if` `(isPossible(a, b, n, k)) ` `    ``Console.WriteLine(``"Yes"``); ` `    ``else` `    ``Console.WriteLine(``"No"``); ` `} ` `} ` ` `  `// This code is contributed by anuj_67. `

## PHP

 `= k. ` ` `  `// Check wheather any permutation  ` `// exists which satisfy the condition. ` `function` `isPossible( ``\$a``, ``\$b``, ``\$n``, ``\$k``) ` `{ ` `     `  `    ``// Sort the array a[] in ` `    ``// decreasing order. ` `    ``sort(``\$a``); ` ` `  `    ``// Sort the array b[] in  ` `    ``// increasing order. ` `    ``rsort(``\$b``); ` ` `  `    ``// Checking condition on each ` `    ``// index. ` `    ``for` `( ``\$i` `= 0; ``\$i` `< ``\$n``; ``\$i``++) ` `        ``if` `(``\$a``[``\$i``] + ``\$b``[``\$i``] < ``\$k``) ` `            ``return` `false; ` ` `  `    ``return` `true; ` `} ` ` `  `// Driven Program ` `    ``\$a` `= ``array``( 2, 1, 3 ); ` `    ``\$b` `= ``array``( 7, 8, 9 ); ` `    ``\$k` `= 10; ` `    ``\$n` `= ``count``(``\$a``); ` ` `  `    ``if``(isPossible(``\$a``, ``\$b``, ``\$n``, ``\$k``))  ` `        ``echo` `"Yes"` `; ` `    ``else` `        ``echo` `"No"``; ` ` `  `// This code is contributed by  ` `// anuj_67. ` `?> `

Output:

```Yes
```

Time Complexity: O(n log n).

## tags:

Arrays Sorting Arrays Sorting