Given two arrays A[] and B[] consisting of N positive integers, the task is to find the total number of subsets of indices such that the maximum value in the array A[] over all these indices is greater than or equal to the sum of all values over these indices in the array B[].
Examples:
Input: A[] = {3, 1}, B[] = {1, 2}
Output: 2
Explanation:
The total possible valid subsets of indices are {0}, {0, 1}
{0}: max(3) >= sum(1)
{1, 2}: max(1, 3) >= sum(1, 2)Input: A[] = {1, 3, 2, 6}, B[] = {7, 3, 2, 1}
Output: 6
Approach: The above problem can be solved using the concept discussed in the Subset Sum Problem with the help of Dynamic programming. The idea is to create a dp[][] of dimensions N*maximum element of the array A[]. Now, each node of the dp[][] matrix, i.e., dp[i][j] represents the number of subsets of the first i elements having sum j. Follow the below steps to solve this problem:
- Create a variable, say ans as 0 to store the total number of required subsets.
- Create a vector of pairs, say AB, and fill it with the elements of A & B, i.e., AB[i] = {A[i], B[i]}.
- Sort this vector of pairs on the basis of the first element.
- Initially dp table will be filled with zeroes except dp[0][0] = 1.
- Traverse the array AB[] and consider the value of AB[i].first as the maximum because AB is sorted on the first element and it is maximum in the range [0, i] and in each iteration, traverse through all possible sums j and for each iteration calculate the subsets till index i having sum j by including and excluding the current element.
- After completing the above steps, traverse the matrix dp[][] and check how many subsets formed are valid by checking the following conditions. If it is found to be true, then add the value dp[i – 1][j] to the variable ans.
j + AB[i – 1].second <= AB[i].first
- After completing the above steps, print the value of ans 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 number of non-empty// subset of indices such that the maximum// of values over these indices in A is// at least the total sum over B[]int countValidSubsets(int A[], int B[], int N){ int ans = 0; vector<pair<int, int> > AB(N); // Stores the maximum element in // the array A[] int mx = INT_MIN; // Do the DP in 1-based indexing // as there will be no corner case // to handle specifically for (int i = 0; i <= N; i++) { AB[i] = { A[i], B[i] }; mx = max(mx, A[i]); } // Sort the pair vector sort(AB.begin(), AB.end()); // dp matrix where dp[i][j] denotes // total valid subsets upto index // i with sum j vector<vector<int> > dp( N + 1, vector<int>(mx + 1, 0)); dp[0][0] = 1; // Traverse the array AB[] for (int i = 1; i <= N; i++) { for (int j = 0; j <= mx; j++) { // Selecting the current // element in the subset if (j + AB[i - 1].second <= mx) { dp[i][j + AB[i - 1].second] += dp[i - 1][j]; } // Discarding the element dp[i][j] += dp[i - 1][j]; } } // Take the count of valid subsets for (int i = 1; i <= N; ++i) { int cnt = 0; // Iterate through all the // possible subsets for (int j = 0; j <= mx; j++) { // Check if the current subsets // till index i having sum j // are valid if (j + AB[i - 1].second <= AB[i - 1].first) { cnt += dp[i - 1][j]; } } // Update the value of ans ans += cnt; } // Return the total count of subsets return ans;}// Driver Codeint main(){ int A[] = { 1, 3, 2, 6 }; int B[] = { 7, 3, 2, 1 }; int N = sizeof(A) / sizeof(A[0]); cout << countValidSubsets(A, B, N); return 0;} |
Java
// Java program for the above approachimport java.util.*;class GFG{ static class pair { int first, second; public pair(int first, int second) { this.first = first; this.second = second; } } // Function to find the number of non-empty// subset of indices such that the maximum// of values over these indices in A is// at least the total sum over B[]static int countValidSubsets(int A[], int B[], int N){ int ans = 0; pair []AB = new pair[N]; // Stores the maximum element in // the array A[] int mx = Integer.MIN_VALUE; // Do the DP in 1-based indexing // as there will be no corner case // to handle specifically for (int i = 0; i < N; i++) { AB[i] = new pair( A[i], B[i] ); mx = Math.max(mx, A[i]); } // Sort the pair vector Arrays.sort(AB,(a,b)->a.first-b.first); // dp matrix where dp[i][j] denotes // total valid subsets upto index // i with sum j int[][] dp= new int[N + 1][mx + 1]; dp[0][0] = 1; // Traverse the array AB[] for (int i = 1; i <= N; i++) { for (int j = 0; j <= mx; j++) { // Selecting the current // element in the subset if (j + AB[i - 1].second <= mx) { dp[i][j + AB[i - 1].second] += dp[i - 1][j]; } // Discarding the element dp[i][j] += dp[i - 1][j]; } } // Take the count of valid subsets for (int i = 1; i <= N; ++i) { int cnt = 0; // Iterate through all the // possible subsets for (int j = 0; j <= mx; j++) { // Check if the current subsets // till index i having sum j // are valid if (j + AB[i - 1].second <= AB[i - 1].first) { cnt += dp[i - 1][j]; } } // Update the value of ans ans += cnt; } // Return the total count of subsets return ans;}// Driver Codepublic static void main(String[] args){ int A[] = { 1, 3, 2, 6 }; int B[] = { 7, 3, 2, 1 }; int N = A.length; System.out.print(countValidSubsets(A, B, N));}}// This code is contributed by shikhasingrajput |
Python3
# python program for the above approachINT_MIN = -2147483648# Function to find the number of non-empty# subset of indices such that the maximum# of values over these indices in A is# at least the total sum over B[]def countValidSubsets(A, B, N): ans = 0 AB = [[0 for _ in range(2)] for _ in range(N)] # Stores the maximum element in # the array A[] mx = INT_MIN # Do the DP in 1-based indexing # as there will be no corner case # to handle specifically for i in range(0, N): AB[i] = [A[i], B[i]] mx = max(mx, A[i]) # Sort the pair vector AB.sort() # dp matrix where dp[i][j] denotes # total valid subsets upto index # i with sum j dp = [[0 for _ in range(mx+1)] for _ in range(N+1)] dp[0][0] = 1 # Traverse the array AB[] for i in range(1, N+1): for j in range(0, mx+1): # Selecting the current # element in the subset if (j + AB[i - 1][1] <= mx): dp[i][j + AB[i - 1][1]] += dp[i - 1][j] # Discarding the element dp[i][j] += dp[i - 1][j] # Take the count of valid subsets for i in range(1, N+1): cnt = 0 # Iterate through all the # possible subsets for j in range(0, mx+1): # Check if the current subsets # till index i having sum j # are valid if (j + AB[i - 1][1] <= AB[i - 1][0]): cnt += dp[i - 1][j] # Update the value of ans ans += cnt # Return the total count of subsets return ans# Driver Codeif __name__ == "__main__": A = [1, 3, 2, 6] B = [7, 3, 2, 1] N = len(A) print(countValidSubsets(A, B, N)) # This code is contributed by rakeshsahni |
C#
// C# program for the above approachusing System;using System.Linq;public class GFG{ class pair : IComparable<pair> { public int first, second; public pair(int first, int second) { this.first = first; this.second = second; } public int CompareTo(pair p) { return this.first-p.second; } } // Function to find the number of non-empty// subset of indices such that the maximum// of values over these indices in A is// at least the total sum over []Bstatic int countValidSubsets(int []A, int []B, int N){ int ans = 0; pair []AB = new pair[N]; // Stores the maximum element in // the array []A int mx = int.MinValue; // Do the DP in 1-based indexing // as there will be no corner case // to handle specifically for (int i = 0; i < N; i++) { AB[i] = new pair( A[i], B[i] ); mx = Math.Max(mx, A[i]); } // Sort the pair vector Array.Sort(AB); AB.Reverse(); // dp matrix where dp[i,j] denotes // total valid subsets upto index // i with sum j int[,] dp= new int[N + 1,mx + 1]; dp[0,0] = 1; // Traverse the array AB[] for (int i = 1; i <= N; i++) { for (int j = 0; j <= mx; j++) { // Selecting the current // element in the subset if (j + AB[i - 1].second <= mx) { dp[i,j + AB[i - 1].second] += dp[i - 1,j]; } // Discarding the element dp[i,j] += dp[i - 1,j]; } } // Take the count of valid subsets for (int i = 1; i <= N; ++i) { int cnt = 0; // Iterate through all the // possible subsets for (int j = 0; j <= mx; j++) { // Check if the current subsets // till index i having sum j // are valid if (j + AB[i - 1].second <= AB[i - 1].first) { cnt += dp[i - 1,j]; } } // Update the value of ans ans += cnt; } // Return the total count of subsets return ans;}// Driver Codepublic static void Main(String[] args){ int []A = { 1, 3, 2, 6 }; int []B = { 7, 3, 2, 1 }; int N = A.Length; Console.Write(countValidSubsets(A, B, N));}}// This code contributed by shikhasingrajput |
Javascript
<script>// Javascript program for the above approach// Function to find the number of non-empty// subset of indices such that the maximum// of values over these indices in A is// at least the total sum over B[]function countValidSubsets(A, B, N) { let ans = 0; let AB = new Array(N); // Stores the maximum element in // the array A[] let mx = Number.MIN_SAFE_INTEGER; // Do the DP in 1-based indexing // as there will be no corner case // to handle specifically for (let i = 0; i < N; i++) { AB[i] = [A[i], B[i]]; mx = Math.max(mx, A[i]); console.log(A[i]); } // Sort the pair vector AB.sort((a, b) => a - b); // dp matrix where dp[i][j] denotes // total valid subsets upto index // i with sum j let dp = new Array(N + 1).fill(0).map(() => { return new Array(mx + 1).fill(0); }); dp[0][0] = 1; // Traverse the array AB[] for (let i = 1; i <= N; i++) { for (let j = 0; j <= mx; j++) { // Selecting the current // element in the subset if (j + AB[i - 1][1] <= mx) { dp[i][j + AB[i - 1][1]] += dp[i - 1][j]; } // Discarding the element dp[i][j] += dp[i - 1][j]; } } // Take the count of valid subsets for (let i = 1; i <= N; ++i) { let cnt = 0; // Iterate through all the // possible subsets for (let j = 0; j <= mx; j++) { // Check if the current subsets // till index i having sum j // are valid if (j + AB[i - 1][1] <= AB[i - 1][0]) { cnt += dp[i - 1][j]; } } // Update the value of ans ans += cnt; } // Return the total count of subsets return ans;}// Driver Codelet A = [1, 3, 2, 6];let B = [7, 3, 2, 1];let N = A.length;document.write(countValidSubsets(A, B, N));// This code is contributed by gfgking.</script> |
Output:
6
Time Complexity: O(N*M), where M is the maximum element in the array.
Auxiliary Space: O(N*M)
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
