Given two arrays A[] and B[] both consisting of N positive integers, the task is to find the minimum size of the subsets of pair of elements (A[i], B[i]) such that the sum of all the pairs of subsets is at least the sum of remaining array elements A[] which are not including in the subset i.e., (A[0] + B[0] + A[1] + B[1] + … + A[K – 1] + B[K – 1] >= A[K + 1] + … + A[N – 1].
Examples:
Input: A[] = {3, 2, 2}, B[] = {2, 3, 1}
Output: 1
Explanation:
Choose the subset as {(3, 2)}. Now, the sum of subsets is 3 + 2 = 5, which greater than sum of remaining A[] = 3 + 1 = 4.Input: A[] = {2, 2, 2, 2, 2}, B[] = {1, 1, 1, 1, 1}
Output: 3
Naive Approach: The simplest approach is to generate all possible subsets of the given pairs of elements and print the size of that subset that satisfies the given criteria and has a minimum size.
Time Complexity: O(2N)
Auxiliary Space: O(1)
Efficient Approach: The given problem can be solved by using the Greedy Approach, the idea is to use sorting and observation can be made that choosing the ith pair as a part of the resultant subset the difference between the 2 subsets decreases by the amount (2*S[i] + U[i]). Follow the steps below to solve the problem:
- Initialize an array, say difference[] of size N that stores the value of (2*A[i] + B[i]) for each pair of elements.
- Initialize a variable, say sum that keeps the track of the sum of remaining array elements A[i].
- Initialize a variable, say K that keeps the track of the size of the resultant subset.
- Iterate over the range [0, N) and update the value of difference[i] as the value of (2*A[i] + B[i]) and decrement the value of sum by the value A[i].
- Sort the given array difference[] in increasing order.
- Traverse the array difference[] in a reverse manner until the sum is negative and add the value of difference[i] to the sum and increment the value of K by 1.
- After completing the above steps, print the value of K as the result.
Below is the implementation of the above approach:
C++
// C++ program for the above approach#include <bits/stdc++.h>using namespace std;// Function to find the minimum size// of subset satisfying given criteriavoid maximizeApples(vector<int>& U, vector<int>& S, int N){ // Stores the value of 2*S[i] + U[i] vector<int> x(N); // Stores the difference between // the 2 subsets int sum = 0; for (int i = 0; i < N; i++) { // Update the value of sum sum -= S[i]; x[i] += 2 * S[i] + U[i]; } // Sort the array X[] in an // ascending order sort(x.begin(), x.end()); int ans = 0; int j = N - 1; // Traverse the array while (sum <= 0) { // Update the value of sum sum += x[j--]; // Increment value of ans ans++; } // Print the resultant ans cout << ans;}// Driver Codeint main(){ vector<int> A = { 1, 1, 1, 1, 1 }; vector<int> B = { 2, 2, 2, 2, 2 }; int N = A.size(); maximizeApples(A, B, N); return 0;} // This code is contributed by rakeshsahni |
Java
// Java program for the above approachimport java.io.*;import java.util.*;class GFG { // Function to find the minimum size // of subset satisfying given criteria private static void maximizeApples( int[] U, int[] S, int N) { // Stores the value of 2*S[i] + U[i] int[] x = new int[N]; // Stores the difference between // the 2 subsets int sum = 0; for (int i = 0; i < N; i++) { // Update the value of sum sum -= S[i]; x[i] += 2 * S[i] + U[i]; } // Sort the array X[] in an // ascending order Arrays.sort(x); int ans = 0; int j = N - 1; // Traverse the array while (sum <= 0) { // Update the value of sum sum += x[j--]; // Increment value of ans ans++; } // Print the resultant ans System.out.println(ans); } // Driver Code public static void main(String[] args) { int[] A = new int[] { 1, 1, 1, 1, 1 }; int[] B = new int[] { 2, 2, 2, 2, 2 }; int N = A.length; maximizeApples(A, B, N); }} |
Python3
# Python program for the above approach# Function to find the minimum size# of subset satisfying given criteriadef maximizeApples(U, S, N): # Stores the value of 2*S[i] + U[i] x = [0]*N # Stores the difference between # the 2 subsets sum = 0 for i in range(N): # Update the value of sum sum -= S[i] x[i] += 2 * S[i] + U[i] # Sort the array X[] in an # ascending order x.sort() ans = 0 j = N - 1 # Traverse the array while sum <= 0: # Update the value of sum sum += x[j] j = j - 1 # Increment value of ans ans = ans + 1 # Print the resultant ans print(ans)# Driver CodeA = [1, 1, 1, 1, 1]B = [2, 2, 2, 2, 2]N = len(A)maximizeApples(A, B, N)# This code is contributed by Potta Lokesh |
C#
// c# program for the above approachusing System.Collections.Generic; using System; class GFG { // Function to find the minimum size // of subset satisfying given criteria static void maximizeApples(int[] U, int[] S, int N) { // Stores the value of 2*S[i] + U[i] List<int> x = new List<int>(); // Stores the difference between // the 2 subsets int sum = 0; for (int i = 0; i < N; i++) { // Update the value of sum sum -= S[i]; x.Add( 2 * S[i] + U[i]); } // Sort the array X[] in an // ascending order x.Sort(); int ans = 0; int j = N - 1; // Traverse the array while (sum <= 0) { // Update the value of sum sum += x[j--]; // Increment value of ans ans++; } // Print the resultant ans Console.WriteLine(ans); } // Driver Code public static void Main() { int[] A = new int[] { 1, 1, 1, 1, 1 }; int[] B = new int[] { 2, 2, 2, 2, 2 }; int N = A.Length; maximizeApples(A, B, N); }}// This code is contributed by amreshkumar3. |
Javascript
<script>// Javascript program for the above approach// Function to find the minimum size// of subset satisfying given criteriafunction maximizeApples(U, S, N) { // Stores the value of 2*S[i] + U[i] let x = new Array(N).fill(0); // Stores the difference between // the 2 subsets let sum = 0; for (let i = 0; i < N; i++) { // Update the value of sum sum -= S[i]; x[i] += 2 * S[i] + U[i]; } // Sort the array X[] in an // ascending order x.sort((a, b) => a - b); let ans = 0; let j = N - 1; // Traverse the array while (sum <= 0) { // Update the value of sum sum += x[j--]; // Increment value of ans ans++; } // Print the resultant ans document.write(ans);}// Driver Codelet A = [1, 1, 1, 1, 1];let B = [2, 2, 2, 2, 2];let N = A.length;maximizeApples(A, B, N);// This code is contributed by gfgking.</script> |
Output:
3
Time Complexity: O(N*log N)
Auxiliary Space: O(N)
Another Approach: To solve this problem is by using binary search. The idea is to binary search for the minimum size of the subset of pairs such that the sum of the pairs is at least the sum of remaining array elements.
The steps for this approach are as follows:
- Calculate the sum of all elements in array A and store it in a variable called totalSum.
- Initialize two pointers, low and high. low is initially set to 0 and high is set to totalSum.
- While low is less than or equal to high, do the following: a. Calculate the mid-point of low and high and store it in a variable called mid. b. Initialize two variables, subsetSum and remainingSum, to 0. c. Iterate through the arrays A and B and for each i-th index, do the following: i. If (A[i] + B[i]) is less than or equal to mid, add it to the subsetSum. ii. Otherwise, add A[i] to the remainingSum. d. If subsetSum is greater than or equal to remainingSum, set high to mid – 1 and store mid in a variable called ans. e. Otherwise, set low to mid + 1.
- Return ans.
Below is the implementation of the above approach:
C++
#include <bits/stdc++.h>using namespace std;int min_subset_size(vector<int>& A, vector<int>& B) { int totalSum = accumulate(A.begin(), A.end(), 0); int low = 0, high = totalSum; int ans = -1; while (low <= high) { int mid = (low + high) / 2; int subsetSum = 0, remainingSum = 0; for (int i = 0; i < A.size(); i++) { if (A[i] + B[i] <= mid) { subsetSum += A[i] + B[i]; } else { remainingSum += A[i]; } } if (subsetSum >= remainingSum) { high = mid - 1; ans = mid; } else { low = mid + 1; } } return ans;}int main() { vector<int> A = {2, 2, 2, 2, 2}; vector<int> B = {1, 1, 1, 1, 1}; cout << min_subset_size(A, B) << endl; // Output: 3 return 0;} |
Java
// Java program to find the minimum subset sizeimport java.util.*;public class Main { public static int minSubsetSize(List<Integer> A, List<Integer> B) { int totalSum = 0; for (int i = 0; i < A.size(); i++) { totalSum += A.get(i); } int low = 0, high = totalSum; int ans = -1; while (low <= high) { int mid = (low + high) / 2; int subsetSum = 0, remainingSum = 0; for (int i = 0; i < A.size(); i++) { if (A.get(i) + B.get(i) <= mid) { subsetSum += A.get(i) + B.get(i); } else { remainingSum += A.get(i); } } if (subsetSum >= remainingSum) { high = mid - 1; ans = mid; } else { low = mid + 1; } } return ans; } // Driver Code public static void main(String[] args) { List<Integer> A = new ArrayList<>(Arrays.asList(2, 2, 2, 2, 2)); List<Integer> B = new ArrayList<>(Arrays.asList(1, 1, 1, 1, 1)); System.out.println(minSubsetSize(A, B)); // Output: 3 }} |
Python3
def min_subset_size(A, B): totalSum = sum(A) low = 0 high = totalSum ans = -1 while low <= high: mid = (low + high) // 2 subsetSum = 0 remainingSum = 0 for i in range(len(A)): if A[i] + B[i] <= mid: subsetSum += A[i] + B[i] else: remainingSum += A[i] if subsetSum >= remainingSum: high = mid - 1 ans = mid else: low = mid + 1 return ansA = [2, 2, 2, 2, 2]B = [1, 1, 1, 1, 1]print(min_subset_size(A, B)) |
C#
using System;using System.Linq;using System.Collections.Generic;public class Program { public static int MinSubsetSize(List<int> A, List<int> B) { int totalSum = A.Sum(); int low = 0, high = totalSum; int ans = -1; while (low <= high) { int mid = (low + high) / 2; int subsetSum = 0, remainingSum = 0; for (int i = 0; i < A.Count; i++) { if (A[i] + B[i] <= mid) { subsetSum += A[i] + B[i]; } else { remainingSum += A[i]; } } if (subsetSum >= remainingSum) { high = mid - 1; ans = mid; } else { low = mid + 1; } } return ans; } public static void Main() { List<int> A = new List<int>{ 2, 2, 2, 2, 2 }; List<int> B = new List<int>{ 1, 1, 1, 1, 1 }; Console.WriteLine(MinSubsetSize(A, B)); // Output: 3 }}// This code is contributed by sarojmcy2e |
Javascript
function min_subset_size(A, B) { let totalSum = A.reduce((a,b) => a + b); let low = 0; let high = totalSum; let ans = -1; while (low <= high) { let mid = Math.floor((low + high) / 2); let subsetSum = 0; let remainingSum = 0; for (let i = 0; i < A.length; i++) { if (A[i] + B[i] <= mid) { subsetSum += A[i] + B[i]; } else { remainingSum += A[i]; } } if (subsetSum >= remainingSum) { high = mid - 1; ans = mid; } else { low = mid + 1; } } return ans;}let A = [2, 2, 2, 2, 2];let B = [1, 1, 1, 1,1];console.log(min_subset_size(A, B)); |
Output
3
Time complexity: O(N*log(totalSum))
Auxiliary space: O(N)
Share your thoughts in the comments
