Given two arrays A[] and B[] of size N and an integer K, the task is to check if all possible subset-sums of subsets of size K of the array A[] are greater than that of the array B[] or not. If found to be true, then print “YES”. Otherwise, print “NO”.
Examples:
Input: A[] = {12, 11, 10, 13}, B[] = {7, 10, 6, 2}, K = 3
Output: YES
Explanation: All possible subset sum of size K(= 3) in A[] are {33, 36, 35, 34}.
All possible subset sum of size K(= 3) in B[] are {23, 19, 15, 18}.
Since all subset-sums of size K in the array A[] is greater than all possible subset-sums of size K in the array B[], the required output is “YES”.Input : A[] = {5, 3, 3, 4, 4, 6, 1}, B[] = {9, 10, 9, 8, 4, 6, 2}, K = 6
Output : NO
Naive Approach: The simplest approach to solve this problem is to generate all possible subsets of size K from the arrays A[] and B[] and calculate their respective sums. Check if all the sums obtained in array A[] exceeds that of array B[] or not. If found to be true, then print “YES”. Otherwise, print “NO”.
Time Complexity: O(K × N2K)
Auxiliary Space: O(NK)
Efficient Approach: To optimize the above approach, the idea is based on the fact that if the smallest subset-sum of size K of the array A[] is greater than the largest subset-sum of size K of the array B[], then print “YES”. Otherwise, print “NO”. Follow the steps below to solve the problem:
- Sort the array A[] in ascending order.
- Sort the array B[] in descending order.
- Traverse the array and check if the sum of the first K elements of the array A[] is greater than the sum of the first K elements of the array B[] or not. If found to be true, then print “YES”. Otherwise, print “NO”.
Below is the implementation of the above approach;
C++
// C++ program to implement// the above approach#include <bits/stdc++.h>using namespace std;// Function to check all subset-sums// of K-length subsets in A[] is greater// that in the array B[] or notbool checkSubsetSum(int A[], int B[], int N, int K){ // Sort the array in // ascending order sort(A, A + N); // Sort the array in // descending order sort(B, B + N, greater<int>()); // Stores sum of first K // elements of A[] int sum1 = 0; // Stores sum of first K // elements of B[] int sum2 = 0; // Traverse both the arrays for (int i = 0; i < K; i++) { // Update sum1 sum1 += A[i]; // Update sum2 sum2 += B[i]; } // If sum1 exceeds sum2 if (sum1 > sum2) { return true; } return false;}// Driver Codeint main(){ int A[] = { 12, 11, 10, 13 }; int B[] = { 7, 10, 6, 2 }; int N = sizeof(A) / sizeof(A[0]); int K = 3; if (checkSubsetSum(A, B, N, K)) { cout << "YES"; } else { cout << "NO"; } return 0;} |
Java
// Java program to implement // the above approach import java.util.*; class GFG{ // Function reverses the elements of the arraystatic void reverse(int myArray[]){ Collections.reverse(Arrays.asList(myArray));} // Function to check all subset-sums// of K-length subsets in A[] is greater// that in the array B[] or notstatic boolean checkSubsetSum(int A[], int B[], int N, int K){ // Sort the array in // ascending order Arrays.sort(A); // Sort the array in // descending order Arrays.sort(B); reverse(B); // Stores sum of first K // elements of A[] int sum1 = 0; // Stores sum of first K // elements of B[] int sum2 = 0; // Traverse both the arrays for(int i = 0; i < K; i++) { // Update sum1 sum1 += A[i]; // Update sum2 sum2 += B[i]; } // If sum1 exceeds sum2 if (sum1 > sum2) { return true; } return false;} // Driver Codepublic static void main(String[] args){ int A[] = { 12, 11, 10, 13 }; int B[] = { 7, 10, 6, 2 }; int N = A.length; int K = 3; if (checkSubsetSum(A, B, N, K)) { System.out.print("YES"); } else { System.out.print("NO"); }}}// This code is contributed by susmitakundugoaldanga |
Python3
# Python3 program to implement# the above approach# Function to check all subset-sums# of K-length subsets in A[] is greater# that in the array B[] or notdef checkSubsetSum(A, B, N, K): # Sort the array in # ascending order A.sort() # Sort the array in # descending order B.sort(reverse = True) # Stores sum of first K # elements of A[] sum1 = 0 # Stores sum of first K # elements of B[] sum2 = 0 # Traverse both the arrays for i in range(K): # Update sum1 sum1 += A[i] # Update sum2 sum2 += B[i] # If sum1 exceeds sum2 if (sum1 > sum2): return True return False# Driver CodeA = [ 12, 11, 10, 13 ]B = [ 7, 10, 6, 2]N = len(A)K = 3if (checkSubsetSum(A, B, N, K)): print("Yes")else: print("No")# This code is contributed by avanitrachhadiya2155 |
C#
// C# program to implement // the above approach using System;public class GFG{ // Function reverses the elements of the arraystatic void reverse(int []myArray){ Array.Sort(myArray); Array.Reverse(myArray);} // Function to check all subset-sums// of K-length subsets in []A is greater// that in the array []B or notstatic bool checkSubsetSum(int []A, int []B, int N, int K){ // Sort the array in // ascending order Array.Sort(A); // Sort the array in // descending order Array.Sort(B); reverse(B); // Stores sum of first K // elements of []A int sum1 = 0; // Stores sum of first K // elements of []B int sum2 = 0; // Traverse both the arrays for(int i = 0; i < K; i++) { // Update sum1 sum1 += A[i]; // Update sum2 sum2 += B[i]; } // If sum1 exceeds sum2 if (sum1 > sum2) { return true; } return false;} // Driver Codepublic static void Main(String[] args){ int []A = { 12, 11, 10, 13 }; int []B = { 7, 10, 6, 2 }; int N = A.Length; int K = 3; if (checkSubsetSum(A, B, N, K)) { Console.Write("YES"); } else { Console.Write("NO"); }}}// This code is contributed by 29AjayKumar |
Javascript
<script>// JavaScript program to implement// the above approach// Function to check all subset-sums// of K-length subsets in A[] is greater// that in the array B[] or notfunction checkSubsetSum(A, B, N, K){ // Sort the array in // ascending order A.sort((a,b)=> a-b); // Sort the array in // descending order B.sort((a,b)=>b-a); // Stores sum of first K // elements of A[] var sum1 = 0; // Stores sum of first K // elements of B[] var sum2 = 0; // Traverse both the arrays for (var i = 0; i < K; i++) { // Update sum1 sum1 += A[i]; // Update sum2 sum2 += B[i]; } // If sum1 exceeds sum2 if (sum1 > sum2) { return true; } return false;}// Driver Codevar A = [12, 11, 10, 13];var B = [7, 10, 6, 2];var N = A.length;var K = 3;if (checkSubsetSum(A, B, N, K)) { document.write( "YES");}else { document.write( "NO");}</script> |
YES
Time Complexity: O(N * log(N)
Auxiliary Space: O(1)
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!