Length of Smallest Subsequence such that sum of elements is greater than equal to K
Given an array arr[] of size N and a number K, the task is to find the length of the smallest subsequence such that the sum of the subsequence is greater than or equal to number K.
Example:
Input: arr[] = {2, 3, 1, 5, 6, 3, 7, 9, 14, 10, 2, 5}, K = 35
Output: 4
Smallest subsequence with the sum greater than or equal to the given sum K is {7, 9, 14, 10}
Input: arr[] = {1, 2, 2, 2, 3, 4, 5, 4, 7, 6, 5, 12}, K = 70
Output:-1
Subsequence with sum greater than equal to the given sum is not possible.
Approach:
- This problem can be solved with the help of priority queue
- Traverse input array and insert every array element into priority queue.
- Initialize variables that holds the sum of picked element from priority queue and the variable to get the count of picked element from priority queue to 0
- Pop the elements out from the priority queue until the priority queue is not empty
- Add the element into the sum
- Increase the count because the element is picked to contribute to the total sum
- Check if the sum is greater than the given number K, If yes then stop checking and output the count.
Below is the implementation of above approach.
C++
// C++ implementation to find length of smallest // subsequence such that sum of elements // is greater than equal to given number K #include <bits/stdc++.h> using namespace std; // Function to find the smallest // subsequence such that sum of elements // is greater than equal to given number K int lengthOfSmallestSubsequence( int K, vector< int > v) { // Initialize priority queue priority_queue< int > pq; // Loop to insert all elements into // the priority queue for ( int i = 0; i < v.size(); i++) { pq.push(v[i]); } int sum = 0, count = 0; // Loop to find the smallest // subsequence such that sum of elements // is greater than equal to given number K while (!pq.empty() && sum < K) { sum += pq.top(); pq.pop(); count++; } // If sum is less than K // then return -1 else return count. if (sum < K) { return -1; } return count; } // Driver code int main() { vector< int > v{ 2, 3, 1, 5, 6, 3, 7, 9, 14, 10, 2, 5 }; int K = 35; cout << lengthOfSmallestSubsequence(K, v); return 0; } |
Java
// Java implementation to find length of smallest // subsequence such that sum of elements // is greater than equal to given number K import java.util.*; class GFG { // Function to find the smallest // subsequence such that sum of elements // is greater than equal to given number K static int lengthOfSmallestSubsequence( int K, int []v) { // Initialize priority queue Queue<Integer> pq = new PriorityQueue<Integer>(Collections.reverseOrder()); // Loop to insert all elements into // the priority queue for ( int i = 0 ; i < v.length; i++) { pq.add(v[i]); } int sum = 0 , count = 0 ; // Loop to find the smallest // subsequence such that sum of elements // is greater than equal to given number K while (!pq.isEmpty() && sum < K) { sum += pq.peek(); pq.remove(); count++; } // If sum is less than K // then return -1 else return count. if (sum < K) { return - 1 ; } return count; } // Driver code public static void main(String[] args) { int []v = { 2 , 3 , 1 , 5 , 6 , 3 , 7 , 9 , 14 , 10 , 2 , 5 }; int K = 35 ; System.out.print(lengthOfSmallestSubsequence(K, v)); } } // This code is contributed by Rajput-Ji |
Python3
# Python3 implementation to find length of smallest # subsequence such that sum of elements # is greater than equal to given number K # Function to find the smallest # subsequence such that sum of elements # is greater than equal to given number K def lengthOfSmallestSubsequence(K, v): # Initialize priority queue pq = [] # Loop to insert all elements into # the priority queue for i in v: pq.append(i) pq.sort() sum = 0 count = 0 # Loop to find the smallest # subsequence such that sum of elements # is greater than equal to given number K while ( len (pq) > 0 and sum < K): sum + = pq[ - 1 ] del pq[ - 1 ] count + = 1 # If sum is less than K # then return -1 else return count. if ( sum < K): return - 1 return count # Driver code v = [ 2 , 3 , 1 , 5 , 6 , 3 , 7 , 9 , 14 , 10 , 2 , 5 ] K = 35 print (lengthOfSmallestSubsequence(K, v)) # This code is contributed by mohit kumar 29 |
C#
// C# implementation to find length of smallest // subsequence such that sum of elements // is greater than equal to given number K using System; using System; using System.Collections.Generic; using System.Linq; class GFG { // Function to find the smallest // subsequence such that sum of elements // is greater than equal to given number K static int lengthOfSmallestSubsequence( int K, int []v) { // Initialize List List< int > pq = new List< int >(); // Loop to insert all elements into // the List for ( int i = 0; i < v.Length; i++) { pq.Add(v[i]); } // Sort list in reverse order pq.Sort(); pq.Reverse(); int sum = 0; int count = 0; // Loop to find the smallest // subsequence such that sum of elements // is greater than equal to given number K while (pq.Count > 0 && sum < K) { sum += pq[0]; pq.RemoveAt(0); count++; } // If sum is less than K // then return -1 else return count. if (sum < K) { return -1; } return count; } // Driver code static public void Main () { int []v = { 2, 3, 1, 5,6, 3, 7, 9, 14, 10, 2, 5 }; int K = 35; Console.WriteLine(lengthOfSmallestSubsequence(K, v)); } } // This code is contributed by avanitrachhadiya2155 |
Javascript
<script> // JavaScript implementation to find length of smallest // subsequence such that sum of elements // is greater than equal to given number K using System; // Function to find the smallest // subsequence such that sum of elements // is greater than equal to given number K function lengthOfSmallestSubsequence(K, v) { // Initialize List let pq = new Array(); // Loop to insert all elements into // the List for (let i = 0; i < v.length; i++) { pq.push(v[i]); } // Sort list in reverse order pq.sort((a, b) => b - a); let sum = 0; let count = 0; // Loop to find the smallest // subsequence such that sum of elements // is greater than equal to given number K while (pq.length > 0 && sum < K) { sum += pq[0]; pq.splice(0, 1); count++; } // If sum is less than K // then return -1 else return count. if (sum < K) { return -1; } return count; } // Driver code let v = [2, 3, 1, 5, 6, 3, 7, 9, 14, 10, 2, 5]; let K = 35; document.write(lengthOfSmallestSubsequence(K, v)); // This code is contributed by gfgking </script> |
Output:
4