Given an array arr[] consisting of N integers and an integer K, the task is to find the sum of the length of the two smallest unique subsets having sum of its elements at least K.
Examples:
Input: arr[] = {2, 4, 5, 6, 7, 8}, K = 16
Output: 6
Explanation:
The subsets {2, 6, 8} and {4, 5, 7} are the two smallest subsets with sum K(= 16).
Therefore, the sum of the lengths of both these subsets = 3 + 3 = 6.Input: arr[] = {14, 3, 7, 8, 9, 7, 12, 15, 10, 6}, K = 40
Output: 8
Approach: The given problem can be solved based on the following observations:
- Sorting the array reduces the problem to choosing a subarray whose sum is at least K between the range of indices [i, N], and then check, if the sum of the remaining array elements in the range of indices [i, N] is K or not.
- To implement the above idea, a 2D array, say dp[][], is used such that dp[i][j] stores the minimum sum of the subset over the range of indices [i, N] having a value at least j. Then the transition state is similar to 0/1 Knapsack that can be defined as:
- If the value of arr[i] is greater than j, then update dp[i][j] to arr[i].
- Otherwise, update dp[i][j] to the minimum of dp[i + 1][j] and (dp[i + 1][j – arr[i]] + arr[i]).
Follow the steps below to solve the problem:
- Sort the array in ascending order.
- Initialize an array, say suffix[], and store the suffix sum of the array arr[] in it.
- Initialize a 2D array, say dp[][], such that dp[i][j] stores the minimum sum of the subset over the range of indices [i, N] having a value at least j.
- Initialize dp[N][0] as 0 and all other states as INT_MAX.
- Traverse the array arr[i] in reverse order and perform the following steps:
- Iterate over the range of indices [0, K] in reverse order and perform the following operations:
- If the value of arr[i] is at least j, then update the value of dp[i][j] as arr[i] as the current state has sum at least j. Now, continue the iteration.
- If the value of next state, i.e., dp[i + 1][j – arr[i]] is INT_MAX, then update dp[i][j] as INT_MAX.
- Otherwise, update dp[i][j] as the minimum of dp[i + 1][j] and (dp[i + 1][j – arr[i]] + arr[i]) to store the sum of all values having sum at least j.
- Iterate over the range of indices [0, K] in reverse order and perform the following operations:
- Now, traverse the array suffix[] in reverse order and if the value of (suffix[i] – dp[i][K]) is at least K, then print (N – i) as the sum of the size of the two smallest subsets formed and break out of the loop.
- Otherwise, print “-1”.
Below is the implementation of the above approach:
C++
// C++ program for the above approach#include <bits/stdc++.h>using namespace std;const int MAX = 1e9;// Function to calculate sum of lengths// of two smallest subsets with sum >= Kint MinimumLength(int A[], int N, int K){ // Sort the array in ascending order sort(A, A + N); // Stores suffix sum of the array int suffix[N + 1] = { 0 }; // Update the suffix sum array for (int i = N - 1; i >= 0; i--) suffix[i] = suffix[i + 1] + A[i]; // Stores all dp-states int dp[N + 1][K + 1]; // Initialize all dp-states // with a maximum possible value for (int i = 0; i <= N; i++) for (int j = 0; j <= K; j++) dp[i][j] = MAX; // Base Case dp[N][0] = 0; // Traverse the array arr[] for (int i = N - 1; i >= 0; i--) { // Iterate over the range [0, K] for (int j = K; j >= 0; j--) { // If A[i] is equal to at // least the required sum // j for the current state if (j <= A[i]) { dp[i][j] = A[i]; continue; } // If the next possible // state doesn't exist if (dp[i + 1][j - A[i]] == MAX) dp[i][j] = MAX; // Otherwise, update the current // state to the minimum of the // next state and state including // the current element A[i] else dp[i][j] = min(dp[i + 1][j], dp[i + 1][j - A[i]] + A[i]); } } // Traverse the suffix sum array for (int i = N - 1; i >= 0; i--) { // If suffix[i] - dp[i][K] >= K if (suffix[i] - dp[i][K] >= K) { // Sum of lengths of the two // smallest subsets is obtained return N - i; } } // Return -1, if there doesn't // exist any subset of sum >= K return -1;}// Driver Codeint main(){ int arr[] = { 7, 4, 5, 6, 8 }; int K = 13; int N = sizeof(arr) / sizeof(arr[0]); cout << MinimumLength(arr, N, K); return 0;} |
Java
// Java program for the above approachimport java.io.*;import java.lang.*;import java.util.*;class GFG{static int MAX = (int)(1e9);// Function to calculate sum of lengths// of two smallest subsets with sum >= Kstatic int MinimumLength(int A[], int N, int K){ // Sort the array in ascending order Arrays.sort(A); // Stores suffix sum of the array int suffix[] = new int[N + 1]; // Update the suffix sum array for(int i = N - 1; i >= 0; i--) suffix[i] = suffix[i + 1] + A[i]; // Stores all dp-states int dp[][] = new int[N + 1][K + 1]; // Initialize all dp-states // with a maximum possible value for(int i = 0; i <= N; i++) for(int j = 0; j <= K; j++) dp[i][j] = MAX; // Base Case dp[N][0] = 0; // Traverse the array arr[] for(int i = N - 1; i >= 0; i--) { // Iterate over the range [0, K] for(int j = K; j >= 0; j--) { // If A[i] is equal to at // least the required sum // j for the current state if (j <= A[i]) { dp[i][j] = A[i]; continue; } // If the next possible // state doesn't exist if (dp[i + 1][j - A[i]] == MAX) dp[i][j] = MAX; // Otherwise, update the current // state to the minimum of the // next state and state including // the current element A[i] else dp[i][j] = Math.min(dp[i + 1][j], dp[i + 1][j - A[i]] + A[i]); } } // Traverse the suffix sum array for(int i = N - 1; i >= 0; i--) { // If suffix[i] - dp[i][K] >= K if (suffix[i] - dp[i][K] >= K) { // Sum of lengths of the two // smallest subsets is obtained return N - i; } } // Return -1, if there doesn't // exist any subset of sum >= K return -1;}// Driver Codepublic static void main(String[] args){ int arr[] = { 7, 4, 5, 6, 8 }; int K = 13; int N = arr.length; System.out.println(MinimumLength(arr, N, K));}}// This code is contributed by Kingash |
Python3
# Python3 program for the above approachMAX = 1e9# Function to calculate sum of lengths# of two smallest subsets with sum >= Kdef MinimumLength(A, N, K): # Sort the array in ascending order A.sort() # Stores suffix sum of the array suffix = [0] * (N + 1) # Update the suffix sum array for i in range(N - 1, -1, -1): suffix[i] = suffix[i + 1] + A[i] # Stores all dp-states dp = [[0] * (K + 1)] * (N + 1) # Initialize all dp-states # with a maximum possible value for i in range(N + 1): for j in range(K + 1): dp[i][j] = MAX # Base Case dp[N][0] = 0 # Traverse the array arr[] for i in range(N - 1, -1, -1): # Iterate over the range [0, K] for j in range(K, -1, -1): # If A[i] is equal to at # least the required sum # j for the current state if (j <= A[i]) : dp[i][j] = A[i] continue # If the next possible # state doesn't exist if (dp[i + 1][j - A[i]] == MAX): dp[i][j] = MAX # Otherwise, update the current # state to the minimum of the # next state and state including # the current element A[i] else : dp[i][j] = min(dp[i + 1][j], dp[i + 1][j - A[i]] + A[i]) # Traverse the suffix sum array for i in range(N - 1, -1, -1): # If suffix[i] - dp[i][K] >= K if (suffix[i] - dp[i][K] >= K): # Sum of lengths of the two # smallest subsets is obtained return N - i # Return -1, if there doesn't # exist any subset of sum >= K return -1# Driver Codearr = [ 7, 4, 5, 6, 8 ]K = 13N = len(arr) print(MinimumLength(arr, N, K))# This code is contributed by splevel62 |
C#
// C# program for the above approachusing System;class GFG{static int MAX = (int)(1e9);// Function to calculate sum of lengths// of two smallest subsets with sum >= Kstatic int MinimumLength(int[] A, int N, int K){ // Sort the array in ascending order Array.Sort(A); // Stores suffix sum of the array int[] suffix = new int[N + 1]; // Update the suffix sum array for(int i = N - 1; i >= 0; i--) suffix[i] = suffix[i + 1] + A[i]; // Stores all dp-states int[,] dp = new int[N + 1, K + 1]; // Initialize all dp-states // with a maximum possible value for(int i = 0; i <= N; i++) for(int j = 0; j <= K; j++) dp[i, j] = MAX; // Base Case dp[N, 0] = 0; // Traverse the array arr[] for(int i = N - 1; i >= 0; i--) { // Iterate over the range [0, K] for(int j = K; j >= 0; j--) { // If A[i] is equal to at // least the required sum // j for the current state if (j <= A[i]) { dp[i, j] = A[i]; continue; } // If the next possible // state doesn't exist if (dp[i + 1, j - A[i]] == MAX) dp[i, j] = MAX; // Otherwise, update the current // state to the minimum of the // next state and state including // the current element A[i] else dp[i, j] = Math.Min(dp[i + 1, j], dp[i + 1, j - A[i]] + A[i]); } } // Traverse the suffix sum array for(int i = N - 1; i >= 0; i--) { // If suffix[i] - dp[i][K] >= K if (suffix[i] - dp[i, K] >= K) { // Sum of lengths of the two // smallest subsets is obtained return N - i; } } // Return -1, if there doesn't // exist any subset of sum >= K return -1;}// Driver Codepublic static void Main(string[] args){ int[] arr = { 7, 4, 5, 6, 8 }; int K = 13; int N = arr.Length; Console.WriteLine(MinimumLength(arr, N, K));}}// This code is contributed by ukasp |
Javascript
<script>// javascript program for the above approachvar max1 = 1000000000;// Function to calculate sum of lengths// of two smallest subsets with sum >= Kfunction MinimumLength(A, N, K){0 // Sort the array in ascending order A.sort(); // Stores suffix sum of the array var suffix = Array(N + 1).fill(0); var i; // Update the suffix sum array for (i = N - 1; i >= 0; i--) suffix[i] = suffix[i + 1] + A[i]; // Stores all dp-states var dp = new Array(N + 1); for (i = 0; i < N+1; i++) dp[i] = new Array(K + 1); // Initialize all dp-states // with a max1imum possible value var j; for (i = 0; i <= N; i++) { for (j = 0; j <= K; j++){ dp[i][j] = max1; } }; // Base Case dp[N][0] = 0; // Traverse the array arr[] for (i = N - 1; i >= 0; i--) { // Iterate over the range [0, K] for (j = K; j >= 0; j--) { // If A[i] is equal to at // least the required sum // j for the current state if (j <= A[i]) { dp[i][j] = A[i]; continue; } // If the next possible // state doesn't exist if (dp[i + 1][j - A[i]] == max1) dp[i][j] = max1; // Otherwise, update the current // state to the minimum of the // next state and state including // the current element A[i] else dp[i][j] = Math.min(dp[i + 1][j], dp[i + 1][j - A[i]] + A[i]); } } // Traverse the suffix sum array for (i = N - 1; i >= 0; i--) { // If suffix[i] - dp[i][K] >= K if (suffix[i] - dp[i][K] >= K) { // Sum of lengths of the two // smallest subsets is obtained return N - i; } } // Return -1, if there doesn't // exist any subset of sum >= K return -1;}// Driver Code var arr = [7, 4, 5, 6, 8]; var K = 13; var N = arr.length; document.write(MinimumLength(arr, N, K));// This code is contributed by SURENDRA_GANGWAR.</script> |
Output:
4
Time Complexity: O(N * K)
Auxiliary Space: O(N * K)
Efficient Approach : using array instead of 2d matrix to optimize space complexity
In previous code we can se that dp[i][j] is dependent upon dp[i+1][j-1] or dp[i][j-1] so we can assume that dp[i+1] is next and dp[i] is current row.
Implementations Steps :
- Sort the array in ascending order and calculates the suffix sum of the array.
- Initializes two vectors curr and next with a maximum possible value, where curr represents the current state, and next represents the next state.
- Set the base case of curr and next vectors as 0 for the 0th index and traverses the array from N-1 index to 0.
- For each element A[i] in the array, it iterates over the range [0, K] in reverse order and updates the curr vector by choosing the minimum length of subsets with sum greater than or equal to K. It uses the next vector to calculate the minimum value.
- Now Updates the next vector as the curr vector.
- Finally traverses the suffix sum array in reverse order and finds the sum of lengths of two smallest subsets that have sum greater than or equal to K.
- Returns the sum of lengths if it is greater than or equal to K, otherwise, it returns -1.
Implementation :
C++
// C++ program for the above approach#include <bits/stdc++.h>using namespace std;const int MAX = 1e9;// Function to calculate sum of lengths// of two smallest subsets with sum >= Kint MinimumLength(int A[], int N, int K){ // Sort the array in ascending order sort(A, A + N); // Stores suffix sum of the array int suffix[N + 1] = { 0 }; // Update the suffix sum array for (int i = N - 1; i >= 0; i--) suffix[i] = suffix[i + 1] + A[i]; // Initialize all dp-states // with a maximum possible value vector<int>curr(K+1 , MAX); vector<int>next(K+1 , MAX); // Base Case curr[0] = 0; next[0] = 0; // Traverse the array arr[] for (int i = N - 1; i >= 0; i--) { // Iterate over the range [0, K] for (int j = K; j >= 0; j--) { // If A[i] is equal to at // least the required sum // j for the current state if (j <= A[i]) { curr[j] = A[i]; continue; } // If the next possible // state doesn't exist if (next[j - A[i]] == MAX) curr[j] = MAX; // Otherwise, update the current // state to the minimum of the // next state and state including // the current element A[i] else curr[j] = min(next[j], next[j - A[i]] + A[i]); } next = curr; } // Traverse the suffix sum array for (int i = N - 1; i >= 0; i--) { // If suffix[i] - dp[i][K] >= K if (suffix[i] - curr[K] >= K) { // Sum of lengths of the two // smallest subsets is obtained return N - i; } } // Return -1, if there doesn't // exist any subset of sum >= K return -1;}// Driver Codeint main(){ int arr[] = { 7, 4, 5, 6, 8 }; int K = 13; int N = sizeof(arr) / sizeof(arr[0]); cout << MinimumLength(arr, N, K); return 0;}// this code is contributed by bhardwajji |
Java
import java.util.Arrays;public class Main { static final int MAX = (int) 1e9; // Function to calculate sum of lengths // of two smallest subsets with sum >= K static int MinimumLength(int[] A, int N, int K) { // Sort the array in ascending order Arrays.sort(A); // Stores suffix sum of the array int[] suffix = new int[N + 1]; // Update the suffix sum array for (int i = N - 1; i >= 0; i--) suffix[i] = suffix[i + 1] + A[i]; // Initialize all dp-states // with a maximum possible value int[] curr = new int[K + 1]; Arrays.fill(curr, MAX); int[] next = new int[K + 1]; Arrays.fill(next, MAX); // Base Case curr[0] = 0; next[0] = 0; // Traverse the array arr[] for (int i = N - 1; i >= 0; i--) { // Iterate over the range [0, K] for (int j = K; j >= 0; j--) { if (j <= A[i]) { curr[j] = A[i]; continue; } // If the next possible // state doesn't exist if (next[j - A[i]] == MAX) curr[j] = MAX; else curr[j] = Math.min(next[j], next[j - A[i]] + A[i]); } next = curr.clone(); } // Traverse the suffix sum array for (int i = N - 1; i >= 0; i--) { // If suffix[i] - dp[i][K] >= K if (suffix[i] - curr[K] >= K) { // Sum of lengths of the two // smallest subsets is obtained return N - i; } } // Return -1, if there doesn't // exist any subset of sum >= K return -1; } public static void main(String[] args) { int[] arr = {7, 4, 5, 6, 8}; int K = 13; int N = arr.length; System.out.println(MinimumLength(arr, N, K)); }} |
Javascript
const MAX = 1e9;// Function to calculate sum of lengths// of two smallest subsets with sum >= Kfunction MinimumLength(A, N, K) { // Sort the array in ascending order A.sort((a, b) => a - b); // Stores suffix sum of the array let suffix = Array(N + 1).fill(0); // Update the suffix sum array for (let i = N - 1; i >= 0; i--) suffix[i] = suffix[i + 1] + A[i]; // Initialize all dp-states // with a maximum possible value let curr = Array(K + 1).fill(MAX); let next = Array(K + 1).fill(MAX); // Base Case curr[0] = 0; next[0] = 0; // Traverse the array arr[] for (let i = N - 1; i >= 0; i--) { // Iterate over the range [0, K] for (let j = K; j >= 0; j--) { // If A[i] is equal to at // least the required sum // j for the current state if (j <= A[i]) { curr[j] = A[i]; continue; } // If the next possible // state doesn't exist if (next[j - A[i]] == MAX) curr[j] = MAX; // Otherwise, update the current // state to the minimum of the // next state and state including // the current element A[i] else curr[j] = Math.min(next[j], next[j - A[i]] + A[i]); } next = [...curr]; } // Traverse the suffix sum array for (let i = N - 1; i >= 0; i--) { // If suffix[i] - dp[i][K] >= K if (suffix[i] - curr[K] >= K) { // Sum of lengths of the two // smallest subsets is obtained return N - i; } } // Return -1, if there doesn't // exist any subset of sum >= K return -1;}// Driver Codelet arr = [7, 4, 5, 6, 8];let K = 13;let N = arr.length;console.log(MinimumLength(arr, N, K)); |
Python3
import sysMAX = sys.maxsize# Function to calculate sum of lengths# of two smallest subsets with sum >= Kdef MinimumLength(A, N, K): # Sort the array in ascending order A.sort() # Stores suffix sum of the array suffix = [0] * (N+1) # Update the suffix sum array for i in range(N - 1, -1, -1): suffix[i] = suffix[i + 1] + A[i] # Initialize all dp-states # with a maximum possible value curr = [MAX] * (K+1) next_ = [MAX] * (K+1) # Base Case curr[0] = 0 next_[0] = 0 # Traverse the array arr[] for i in range(N - 1, -1, -1): # Iterate over the range [0, K] for j in range(K, -1, -1): # If A[i] is equal to at # least the required sum # j for the current state if j <= A[i]: curr[j] = A[i] continue # If the next possible # state doesn't exist if next_[j - A[i]] == MAX: curr[j] = MAX # Otherwise, update the current # state to the minimum of the # next state and state including # the current element A[i] else: curr[j] = min(next_[j], next_[j - A[i]] + A[i]) next_ = curr.copy() # Traverse the suffix sum array for i in range(N - 1, -1, -1): # If suffix[i] - dp[i][K] >= K if suffix[i] - curr[K] >= K: # Sum of lengths of the two # smallest subsets is obtained return N - i # Return -1, if there doesn't # exist any subset of sum >= K return -1# Driver Codeif __name__ == "__main__": arr = [7, 4, 5, 6, 8] K = 13 N = len(arr) print(MinimumLength(arr, N, K)) |
C#
using System;using System.Collections.Generic;using System.Linq;public class Program{ static int MAX = 1000000000; // Function to calculate sum of lengths // of two smallest subsets with sum >= K static int MinimumLength(int[] A, int N, int K) { // Sort the array in ascending order Array.Sort(A); // Stores suffix sum of the array int[] suffix = new int[N + 1]; // Update the suffix sum array for (int i = N - 1; i >= 0; i--) suffix[i] = suffix[i + 1] + A[i]; // Initialize all dp-states // with a maximum possible value List<int> curr = new List<int>(Enumerable.Repeat(MAX, K + 1)); List<int> next = new List<int>(Enumerable.Repeat(MAX, K + 1)); // Base Case curr[0] = 0; next[0] = 0; // Traverse the array arr[] for (int i = N - 1; i >= 0; i--) { // Iterate over the range [0, K] for (int j = K; j >= 0; j--) { // If A[i] is equal to at // least the required sum // j for the current state if (j <= A[i]) { curr[j] = A[i]; continue; } // If the next possible // state doesn't exist if (next[j - A[i]] == MAX) curr[j] = MAX; // Otherwise, update the current // state to the minimum of the // next state and state including // the current element A[i] else curr[j] = Math.Min(next[j], next[j - A[i]] + A[i]); } next = new List<int>(curr); } // Traverse the suffix sum array for (int i = N - 1; i >= 0; i--) { // If suffix[i] - dp[i][K] >= K if (suffix[i] - curr[K] >= K) { // Sum of lengths of the two // smallest subsets is obtained return N - i; } } // Return -1, if there doesn't // exist any subset of sum >= K return -1; } // Driver Code public static void Main() { int[] arr = { 7, 4, 5, 6, 8 }; int K = 13; int N = arr.Length; Console.WriteLine(MinimumLength(arr, N, K)); }} |
Output
4
Time Complexity: O(N * K)
Auxiliary Space: O(K)
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!
