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:
- 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 - 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.
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")