HackerRank Permuting Two Arrays Solution

In this post, we will solve HackerRank Permuting Two Arrays Problem Solution.

There are two n-element arrays of integers. A and B. Permute them into some A’ and B’ such that the relation A'[i] + B'[i]k holds for all i where 0 <i<n
There will be q queries consisting of A, B, and k. For each query, return YES if some permutation A’. B’ satisfying the relation exists. Otherwise, return NO.

Example
A = [0,1]
B = [0,2]
k=1
A valid A’, B’ is A’ = [1,0] and B’ = [0,2]: 1+01 and 0+2 > 1. Return YES.

unction Description

Complete the twoArrays function in the editor below. It should return a string, either YES or NO.

twoArrays has the following parameter(s):

  • int k: an integer
  • int A[n]: an array of integers
  • int B[n]: an array of integers

Returns
– string: either YES or NO

Input Format
The first line contains an integer q, the number of queries.
The next q sets of 3 lines are as follows:

  • The first line contains two space-separated integers n and k, the size of both arrays A and B, and the relation variable.
  • The second line contains n space-separated integers A[i].
    The third line contains n space-separated integers B[i].

Sample Input

STDIN       Function
-----       --------
2           q = 2
3 10        A[] and B[] size n = 3, k = 10
2 1 3       A = [2, 1, 3]
7 8 9       B = [7, 8, 9]
4 5         A[] and B[] size n = 4, k = 5
1 2 2 1     A = [1, 2, 2, 1]
3 3 3 4     B = [3, 3, 3, 4]

Sample Output

YES
NO

Explanation
There are two queries:

  1. Permute these into A’ = [1, 2, 3] and B’ [9, 8, 7] so that the following statements = are true:
    о A[0] + B[1]=1+9=10 > k
    A[1]B[1]2+8=10 > k
    о A[2]B[2]=3+7=10 > k
  2. A = [1, 2, 2, 1], B = [3, 3, 3, 4], and k = 5. To permute A and B into a valid A’ and
    B’, there must be at least three numbers in A that are greater than 1.
HackerRank Permuting Two Arrays Problem Solution
HackerRank Permuting Two Arrays Problem Solution

Permuting Two Arrays C Solution

#include <stdio.h>
#include <string.h>
#include <math.h>
#include <stdlib.h>
#define MAX 2000

void mergeSort(int arr[],int low,int mid,int high){

    int i,m,k,l,temp[high-low+3];

    l=low;
    i=0;
    m=mid+1;

    while((l<=mid)&&(m<=high)){

         if(arr[l]<=arr[m]){
             temp[i]=arr[l];
             l++;
         }
         else{
             temp[i]=arr[m];
             m++;
         }
         i++;
    }

    if(l>mid){
         for(k=m;k<=high;k++){
             temp[i]=arr[k];
             i++;
         }
    }
    else{
         for(k=l;k<=mid;k++){
             temp[i]=arr[k];
             i++;
         }
    }
   
    for(k=0,l=low;k<i;k++,l++){
         arr[l]=temp[k];
    }
}
void partition(int arr[],int low,int high){

    int mid;

    if(low<high){
         mid=(low+high)/2;
         partition(arr,low,mid);
         partition(arr,mid+1,high);
         mergeSort(arr,low,mid,high);
    }
}
int main() {
int t,n,k;
    scanf("%d",&t);
    
    int f=1;
    for(int i=0;i<t;i++){
       scanf("%d %d",&n,&k);
    int a[n],b[n]; 
          for(int j=0;j<n;j++)
             scanf("%d",&a[j]);
          for(int j=0;j<n;j++)
             scanf("%d",&b[j]);
          partition(a,0,n-1);
          partition(b,0,n-1);
        for(int j=0;(j<n)&&f;j++)
            if(a[j]+b[n-j-1]<k)
                f=0;
       if(f)
         printf("YES\n");
       else
         printf("NO\n");
            f=1;
    }
           
    /* Enter your code here. Read input from STDIN. Print output to STDOUT */    
    return 0;
}

Permuting Two Arrays C++ Solution

#include <cmath>
#include <cstdio>
#include <vector>
#include <iostream>
#include <algorithm>
using namespace std;


void solve() {
    int N, K;
    cin >> N >> K;
    
    vector<int> A(N), B(N);
    for (int i=0; i<N; ++i)
        cin >> A[i];
    for (int i=0; i<N; ++i)
        cin >> B[i];
    
    sort(A.begin(), A.end());
    sort(B.rbegin(), B.rend());
    
    bool res=true;
    for (int i=0; i<N; ++i)
        res &= ((A[i]+B[i]) >= K);
    
    if (res)
        cout << "YES\n";
    else
        cout << "NO\n";
}

int main() {
    int T;
    cin >> T;
    
    while (T--)
        solve();
    
    return 0;
}

Permuting Two Arrays C Sharp Solution

using System;
using System.Collections.Generic;
using System.IO;
class Solution {
static void Main(string[] args)
        {
            var sr = new StreamReader(Console.OpenStandardInput());
            Console.WriteLine(ListResults(sr));
            Console.ReadLine();
        }

        public static string ListResults(StreamReader sr)
        {
            int T = int.Parse(sr.ReadLine());
            var result = new List<string>();
            for (int t = 0; t < T; t++)
            {
                var temp = sr.ReadLine().Split(' ');
                int N = int.Parse(temp[0]);
                int K = int.Parse(temp[1]);
                List<int> A = ReadArray(sr.ReadLine());
                List<int> B = ReadArray(sr.ReadLine());
                result.Add(HasSumK(A, B, K));
            }
            return string.Join("\r\n", result) + "\r\n";
        }

        private static string HasSumK(List<int> A, List<int> B, int K)
        {
            A.Sort();
            B.Sort();
            for (int i = 0; i < A.Count; i++)
            {
                if (A[i] + B[B.Count - i - 1] < K)
                {
                    return "NO";
                }
                if (A[i] > K || B[i] > K)
                {
                    break;
                }
            }
            return "YES";
        }

        private static List<int> ReadArray(string arr)
        {
            var strArr = arr.Split(' ');
            var result = new List<int>();
            foreach (var item in strArr)
            {
                result.Add(int.Parse(item));
            }
            return result;
        }
}

Permuting Two Arrays Java Solution

import java.io.*;
import java.math.*;
import java.security.*;
import java.text.*;
import java.util.*;
import java.util.concurrent.*;
import java.util.function.*;
import java.util.regex.*;
import java.util.stream.*;
import static java.util.stream.Collectors.joining;
import static java.util.stream.Collectors.toList;

class Result {

    /*
     * Complete the 'twoArrays' function below.
     *
     * The function is expected to return a STRING.
     * The function accepts following parameters:
     *  1. INTEGER k
     *  2. INTEGER_ARRAY A
     *  3. INTEGER_ARRAY B
     */

    public static String twoArrays(int k, List<Integer> A, List<Integer> B) {
    // Write your code here
    String a="YES";
    Collections.sort(A);
    Collections.sort(B,Collections.reverseOrder());
    for(int i=0;i<A.size();i++)
    {
        if(A.get(i)+B.get(i)<k)
        a="NO";
    }
    return a;

    }

}

public class Solution {
    public static void main(String[] args) throws IOException {
        BufferedReader bufferedReader = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bufferedWriter = new BufferedWriter(new FileWriter(System.getenv("OUTPUT_PATH")));

        int q = Integer.parseInt(bufferedReader.readLine().trim());

        IntStream.range(0, q).forEach(qItr -> {
            try {
                String[] firstMultipleInput = bufferedReader.readLine().replaceAll("\\s+$", "").split(" ");

                int n = Integer.parseInt(firstMultipleInput[0]);

                int k = Integer.parseInt(firstMultipleInput[1]);

                List<Integer> A = Stream.of(bufferedReader.readLine().replaceAll("\\s+$", "").split(" "))
                    .map(Integer::parseInt)
                    .collect(toList());

                List<Integer> B = Stream.of(bufferedReader.readLine().replaceAll("\\s+$", "").split(" "))
                    .map(Integer::parseInt)
                    .collect(toList());

                String result = Result.twoArrays(k, A, B);

                bufferedWriter.write(result);
                bufferedWriter.newLine();
            } catch (IOException ex) {
                throw new RuntimeException(ex);
            }
        });

        bufferedReader.close();
        bufferedWriter.close();
    }
}

Permuting Two Arrays JavaScript Solution

function processData(input) {
    var reg = /\d+/g;
    var cases = parseInt(reg.exec(input)[0]);
    for (var x=0;x<cases;x+=1){
        var ar1=[];
        var ar2=[];
        var len = parseInt(reg.exec(input)[0]);
        var K = parseInt(reg.exec(input)[0]);
        var ans = "YES";
        for (var y=0;y<len;y+=1){
            ar1[y]=parseInt(reg.exec(input)[0]);
        }
        for (var y=0;y<len;y+=1){
            ar2[y]=parseInt(reg.exec(input)[0]);
        } 
        ar1.sort(function(a,b){return a-b});
        ar2.sort(function(a,b){return b-a});
        /*console.log("ar1:",ar1)
        console.log("ar2:",ar2)*/
        for (var y=0;y<len;y+=1){
            if (ar2[y]+ar1[y]<K){
                //console.log(ar2[y],ar1[y],K)
                ans = "NO";
                break;
            }
        }
        console.log(ans);
    }
} 

process.stdin.resume();
process.stdin.setEncoding("ascii");
_input = "";
process.stdin.on("data", function (input) {
    _input += input;
});

process.stdin.on("end", function () {
   processData(_input);
});

Permuting Two Arrays Python Solution

for t in range(int(input())):
    n, k = map(int, input().split())
    a = sorted(map(int, input().split()))
    b = sorted(map(int, input().split()))
    for val in a:
        for i in range(len(b)):
            if val + b[i] >= k:
                b.pop(i)
                break
    print("NO" if b else "YES")