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 to 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 that 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:
C++
// C++ program to check whether permutation of two // arrays satisfy the condition a[i] + b[i] >= k. #include <bits/stdc++.h> using namespace std; // Check whether 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[0]); isPossible(a, b, n, k) ? cout << "Yes" : cout << "No" ; return 0; } // This code is contributed by Aditya Kumar (adityakumar129) |
C
// C program to check whether permutation of two // arrays satisfy the condition a[i] + b[i] >= k. #include <stdbool.h> #include <stdio.h> #include <stdlib.h> // Compare function for qsort for Increasing Order int cmpfunc1( const void * a, const void * b) { return (*( int *)a - *( int *)b); } // Compare function for qsort for decreasing Order int cmpfunc2( const void * a, const void * b) { return (*( int *)b - *( int *)a); } // Check whether any permutation exists which // satisfy the condition. bool isPossible( int a[], int b[], int n, int k) { // Sort the array a[] in decreasing order. qsort (a, n, sizeof ( int ), cmpfunc1); // Sort the array b[] in increasing order. qsort (b, n, sizeof ( int ), cmpfunc2); // 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[0]); isPossible(a, b, n, k) ? printf ( "Yes" ) : printf ( "No" ); return 0; } // This code is contributed by Aditya Kumar (adityakumar129) |
Java
// Java program to check whether // permutation of two arrays satisfy // the condition a[i] + b[i] >= k. import java.util.*; class GFG { // Check whether 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 whether 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
<?php // PHP 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. 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. ?> |
Javascript
<script> // JavaScript 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. function isPossible(a, b, n, k) { // Sort the array a[] // in decreasing order. a.sort( function (a, b){ return a - b}); // Sort the array b[] // in increasing order. b.reverse(); // Checking condition on each index. for (let i = 0; i < n; i++) if (a[i] + b[i] < k) return false ; return true ; } let a = [2, 1, 3]; let b = [7, 8, 9]; let k = 10; let n = a.length; if (isPossible(a, b, n, k)) document.write( "Yes" ); else document.write( "No" ); </script> |
Yes
Time Complexity: O(n log n).
Auxiliary Space: O(1)
This approach is contributed by Anuj Chauhan.
Contact Us