Maximize count of elements that can be selected having minimum difference between their sum and K
Given an array arr[] and an integer value K, the task is to count the maximum number of array elements that can be selected such that:
- Sum of the selected array elements is less than K.
- K – (total sum of selected elements) is greater than or equal to 0 and minimum possible.
Examples:
Examples:
Input: arr[] = {20, 90, 40, 90}, K = 100
Output: 2
Explanation: {20, 40} are selected such that their sum ( = 60) is less than K and K – total sum ( = 40) is greater than 0 and minimum possible.Examples:
Input: arr[] = {30, 30, 10, 10}, K = 50
Output: 3
Explanation: {10, 10, 30} are selected< such that their sum ( = 50) is equal to K and K – total sum is 0 and minimum possible.
Approach: The main idea to solve this problem is to use a Greedy Approach. Follow the steps below to solve this problem:
- Sort the given array.
- Now, starting from the first array element, add the current element to the sum.
- Increment count by 1.
- Check if the sum is greater than the K or not.
- If found to be true, don’t select any more elements.
- Otherwise, repeat the above procedure until the last element of the array has been traversed.
- The answer is the total number of elements selected.
Below is the implementation of the above approach:
C++
// C++ implementation of the above approach #include <bits/stdc++.h> using namespace std; // Function to count maximum number // of elements that can be selected int CountMaximum( int arr[], int n, int k) { // Sort the array sort(arr, arr + n); int sum = 0, count = 0; // Traverse the array for ( int i = 0; i < n; i++) { // Add current element // to the sum sum += arr[i]; // IF sum exceeds k if (sum > k) break ; // Increment count count++; } // Return the count return count; } // Driver Code int main() { int arr[] = { 30, 30, 10, 10 }; int n = sizeof (arr) / sizeof (arr[0]); int k = 50; cout << CountMaximum(arr, n, k); return 0; } |
Java
// Java implementation of the above approach import java.util.Arrays; public class GFG { // Function to count maximum number // of elements that can be selected static int CountMaximum( int arr[], int n, int k) { // Sorting the array Arrays.sort(arr); int sum = 0 , count = 0 ; // Traverse the array for ( int i = 0 ; i < n; i++) { // Add the current // element to the sum sum += arr[i]; // If sum exceeds k if (sum > k) break ; // Increment count count++; } // Returning the count return count; } // Driver code public static void main(String[] args) { int arr[] = { 30 , 30 , 10 , 10 }; int n = 4 ; int k = 50 ; // Function call System.out.println( CountMaximum(arr, n, k)); } } |
Python3
# Python3 implementation of the above approach # Function to count maximum number # of elements that can be selected def CountMaximum(arr, n, k) : # Sort the array arr.sort() Sum , count = 0 , 0 # Traverse the array for i in range ( 0 , n) : # Add current element # to the sum Sum + = arr[i] # IF sum exceeds k if ( Sum > k) : break # Increment count count + = 1 # Return the count return count # Driver code arr = [ 30 , 30 , 10 , 10 ] n = len (arr) k = 50 print (CountMaximum(arr, n, k)) # This code is contributed by divyesh072019 |
C#
// C# implementation of the above approach using System; class GFG { // Function to count maximum number // of elements that can be selected static int CountMaximum( int [] arr, int n, int k) { // Sorting the array Array.Sort(arr); int sum = 0, count = 0; // Traverse the array for ( int i = 0; i < n; i++) { // Add the current // element to the sum sum += arr[i]; // If sum exceeds k if (sum > k) break ; // Increment count count++; } // Returning the count return count; } // Driver code static public void Main() { int [] arr = new int [] { 30, 30, 10, 10 }; int n = 4; int k = 50; // Function call Console.WriteLine(CountMaximum(arr, n, k)); } } // This code is contributed by dharanendralv23 |
Javascript
<script> // Javascript program of the above approach // Function to count maximum number // of elements that can be selected function CountMaximum(arr, n, k) { // Sorting the array arr.sort(); let sum = 0, count = 0; // Traverse the array for (let i = 0; i < n; i++) { // Add the current // element to the sum sum += arr[i]; // If sum exceeds k if (sum > k) break ; // Increment count count++; } // Returning the count return count; } // Driver Code let arr = [ 30, 30, 10, 10 ]; let n = 4; let k = 50; // Function call document.write( CountMaximum(arr, n, k)); </script> |
Time Complexity: O(N log N)
Auxiliary Space: O(1)
C++
// C++ implementation of the above approach #include <bits/stdc++.h> using namespace std; // Function to count maximum number // of elements that can be selected int CountMaximum( int arr[], int n, int k) { // Sort the array sort(arr, arr + n); int sum = 0, count = 0; // Traverse the array for ( int i = 0; i < n; i++) { // Add current element // to the sum sum += arr[i]; // IF sum exceeds k if (sum > k) break ; // Increment count count++; } // Return the count return count; } // Driver Code int main() { int arr[] = { 30, 30, 10, 10 }; int n = sizeof (arr) / sizeof (arr[0]); int k = 50; cout << CountMaximum(arr, n, k); return 0; } |
Java
// Java implementation of the above approach import java.util.Arrays; public class GFG { // Function to count maximum number // of elements that can be selected static int CountMaximum( int arr[], int n, int k) { // Sorting the array Arrays.sort(arr); int sum = 0 , count = 0 ; // Traverse the array for ( int i = 0 ; i < n; i++) { // Add the current // element to the sum sum += arr[i]; // If sum exceeds k if (sum > k) break ; // Increment count count++; } // Returning the count return count; } // Driver code public static void main(String[] args) { int arr[] = { 30 , 30 , 10 , 10 }; int n = 4 ; int k = 50 ; // Function call System.out.println( CountMaximum(arr, n, k)); } } |
Python3
# Python3 implementation of the above approach # Function to count maximum number # of elements that can be selected def CountMaximum(arr, n, k) : # Sort the array arr.sort() Sum , count = 0 , 0 # Traverse the array for i in range ( 0 , n) : # Add current element # to the sum Sum + = arr[i] # IF sum exceeds k if ( Sum > k) : break # Increment count count + = 1 # Return the count return count # Driver code arr = [ 30 , 30 , 10 , 10 ] n = len (arr) k = 50 print (CountMaximum(arr, n, k)) # This code is contributed by divyesh072019 |
C#
// C# implementation of the above approach using System; class GFG { // Function to count maximum number // of elements that can be selected static int CountMaximum( int [] arr, int n, int k) { // Sorting the array Array.Sort(arr); int sum = 0, count = 0; // Traverse the array for ( int i = 0; i < n; i++) { // Add the current // element to the sum sum += arr[i]; // If sum exceeds k if (sum > k) break ; // Increment count count++; } // Returning the count return count; } // Driver code static public void Main() { int [] arr = new int [] { 30, 30, 10, 10 }; int n = 4; int k = 50; // Function call Console.WriteLine(CountMaximum(arr, n, k)); } } // This code is contributed by dharanendralv23 |
Javascript
<script> // Javascript implementation of // the above approach // Function to count maximum number // of elements that can be selected function CountMaximum(arr, n, k) { // Sort the array arr.sort( function (a, b){ return a - b}); let sum = 0, count = 0; // Traverse the array for (let i = 0; i < n; i++) { // Add current element // to the sum sum += arr[i]; // IF sum exceeds k if (sum > k) break ; // Increment count count++; } // Return the count return count; } let arr = [ 30, 30, 10, 10 ]; let n = arr.length; let k = 50; document.write(CountMaximum(arr, n, k)); </script> |
3
Time Complexity: O(N log N)
Auxiliary Space: O(1)