Techgig
Pair Shopping
Shreya is filled with anxiety as she was not able to go shopping for a long time because of covid. Now, she wants to shop her heart out. Her friend Varun is busy with work and is jealous as he is not able to go shopping. Varun gives Shreya a challenge to see if she is a good shopper or not. Shreya has to buy N pairs of crop-top and skirt with the budget limit of M money.
Note: One crop-top and one skirt are together considered a pair.
If Shreya can shop all in the given budget she is considered a good shopper else a bad shopper. As Shreya is all happy and pumped, she might go over budget and needs your help. She will provide you with the prices of crop-tops and skirts and you have to tell her if she can shop that or not.
The challenge is not so simple though. The price of a pair is considered by getting the product of the prices of crop-top and skirt. The total price is the summation of all the prices of pairs. Can you help her?
Note: There might be multiple combinations possible. We are only concerned if shopping is possible or not.
Input Format
- The first line of input consists of number of test cases, T
- The first line of each test case consists two space-separated integers number of crop-tops and skirts, N, and budget, M
- The second line of each test case consists of N space-separated integers representing the price of N crop-tops.
- The third line of each test case consists of N space-separated integers representing the price of N skirts.
Constraints
1<= T <=10
1<= N <=1000
1<= Prices <=1000000
1<= M <=10^15
Output Format
For each test case, print YES if Shreya can shop within budget else print NO.
Sample TestCase 1
JAVA SOLUTION
import java.util.Arrays;
import java.util.Collections;
import java.util.Scanner;
public class CandidateCode {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int t = sc.nextInt();
while (t > 0) {
int n = sc.nextInt();
int m = sc.nextInt();
Integer[] tops = new Integer[n];
int[] skirts = new int[n];
for (int i = 0; i < n; i++) {
tops[i] = sc.nextInt();
}
for (int i = 0; i < n; i++) {
skirts[i] = sc.nextInt();
}
Arrays.sort(tops, Collections.reverseOrder());
Arrays.sort(skirts);
long totalBudget = 0L;
boolean b = true;
for (int i = 0; i < n; i++) {
totalBudget += (long) tops[i] * skirts[i];
System.out.println(tops[i] + "*" + skirts[i] + "=>" + totalBudget);
if (totalBudget > m) {
b = false;
System.out.println("NO");
break;
}
}
if (b) {
System.out.println("YES");
}
--t;
}
}
}