Tutorialspoint.dev

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<bits/stdc++.h>
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[0]);
  
    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

<?php
// PHP program to check whether
// permutation of two arrays satisfy
// the condition a[i] + b[i] >= 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).

Please write comments if you find anything incorrect, or you want to share more information about the topic discussed above.



This article is attributed to GeeksforGeeks.org

You Might Also Like

leave a comment

code

0 Comments

load comments

Subscribe to Our Newsletter