Given an array arr[] of size N and an integer K, the task is to find the maximum and minimum number of elements whose sum is less than equal to K.
Examples:
Input: N = 4, arr[ ] = {6, 2, 1, 3}, K = 7
Output: 3 1
Explanation:
Maximum number of elements whose sum is less than equal to K is 3 i.e [1, 2, 3]
Minimum number of elements whose sum is less than equal to K is 1 i.e [6]Input: N = 5, arr[] = {6, 2, 11, 3, 20}, K = 50
Output: 5 5
Approach: This problem can be solved by sorting the array arr[]. Follow the steps below to solve this problem:
- Sort the array arr[].
- Initialize variable maxNumEle and minNumEle as 0 to store minimum and maximum number of elements whose sum is less than equal to K.
- Initialize a variable cumSum1 to store the cumulative sum of the array arr[].
- Iterate in the range[0, N-1], using the variable i:
- Add current element in cumSum1.
- If cumSum1 is less than equal K, then increment by 1 in maxNumEle, Otherwise break the loop.
- Initialize a variable cumSum2 to store the cumulative sum of the array arr[].
- Iterate in the range[N-1, 0], using the variable i:
- Add current element in cumSum2.
- If cumSum2 is less than equal K, then increment by 1 in minNumEle, Otherwise break the loop.
- After completing the above steps, print the maxNumEle and minNumEle as the answer.
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 maximum// and minimum number of elements// whose sum is less than equal// to Kint findMinMax(int arr[], int N, int K){ // Sorting both arrays sort(arr, arr + N); // To store the minimum and maximum // number of elements whose sum is // less than equal to K int maxNumEle = 0; int minNumEle = 0; // Store the cumulative sum int i, cumSum1 = 0; // Iterate in the range [0, N-1] for (i = 0; i < N; i++) { cumSum1 += arr[i]; // If cumSum1 is less than K if (cumSum1 <= K) maxNumEle += 1; else break; } // Store the cumulative sum int cumSum2 = 0; // Iterate in the range [N-1, 0] for (i = N - 1; i >= 0; i--) { cumSum2 += arr[i]; // If cumSum2 is less than K if (cumSum2 <= K) minNumEle += 1; else break; } // Print the value of maxNumEle and minNumEle cout << maxNumEle << " " << minNumEle;}// Driver Codeint main(){ // Given Input int N = 4; int K = 7; int arr[] = { 6, 2, 1, 3 }; // Function Call findMinMax(arr, N, K); return 0;}// This code is contributed by Potta Lokesh |
Java
// Java program for the above approachimport java.lang.*;import java.util.*;class GFG{// Function to find the maximum// and minimum number of elements// whose sum is less than equal// to Kstatic void findMinMax(int arr[], int N, int K){ // Sorting both arrays Arrays.sort(arr); // To store the minimum and maximum // number of elements whose sum is // less than equal to K int maxNumEle = 0; int minNumEle = 0; // Store the cumulative sum int i, cumSum1 = 0; // Iterate in the range [0, N-1] for(i = 0; i < N; i++) { cumSum1 += arr[i]; // If cumSum1 is less than K if (cumSum1 <= K) maxNumEle += 1; else break; } // Store the cumulative sum int cumSum2 = 0; // Iterate in the range [N-1, 0] for(i = N - 1; i >= 0; i--) { cumSum2 += arr[i]; // If cumSum2 is less than K if (cumSum2 <= K) minNumEle += 1; else break; } // Print the value of maxNumEle and minNumEle System.out.println(maxNumEle + " " + minNumEle);}// Driver codepublic static void main(String[] args){ // Given Input int N = 4; int K = 7; int arr[] = { 6, 2, 1, 3 }; // Function Call findMinMax(arr, N, K);}}// This code is contributed by sanjoy_62 |
Python3
# Python program for the above approach# Function to find the maximum# and minimum number of elements# whose sum is less than equal# to Kdef findMinMax(arr, N, K): # Sorting both arrays arr.sort() # To store the minimum and maximum # number of elements whose sum is # less than equal to K maxNumEle = minNumEle = 0 # Store the cumulative sum cumSum1 = 0 # Iterate in the range [0, N-1] for i in range(N): cumSum1 += arr[i] # If cumSum1 is less than K if cumSum1 <= K: maxNumEle += 1 else: break # Store the cumulative sum cumSum2 = 0 # Iterate in the range [N-1, 0] for i in range(N-1, 0, -1): cumSum2 += arr[i] # If cumSum2 is less than K if cumSum2 <= K: minNumEle += 1 else: break # Print the value of maxNumEle and minNumEle print(maxNumEle, minNumEle) # Driver Code if __name__ == '__main__': # Given Input N = 4 K = 7 arr = [ 6, 2, 1, 3 ] # Function Call findMinMax(arr, N, K) |
C#
// C# program for the above approachusing System;class GFG{ // Function to find the maximum// and minimum number of elements// whose sum is less than equal// to Kstatic void findMinMax(int[] arr, int N, int K){ // Sorting both arrays Array.Sort(arr); // To store the minimum and maximum // number of elements whose sum is // less than equal to K int maxNumEle = 0; int minNumEle = 0; // Store the cumulative sum int i, cumSum1 = 0; // Iterate in the range [0, N-1] for(i = 0; i < N; i++) { cumSum1 += arr[i]; // If cumSum1 is less than K if (cumSum1 <= K) maxNumEle += 1; else break; } // Store the cumulative sum int cumSum2 = 0; // Iterate in the range [N-1, 0] for(i = N - 1; i >= 0; i--) { cumSum2 += arr[i]; // If cumSum2 is less than K if (cumSum2 <= K) minNumEle += 1; else break; } // Print the value of maxNumEle and minNumEle Console.WriteLine(maxNumEle + " " + minNumEle);}// Driver codestatic public void Main(){ // Given Input int N = 4; int K = 7; int[] arr = { 6, 2, 1, 3 }; // Function Call findMinMax(arr, N, K);}}// This code is contributed by target_2 |
Javascript
<script>// Javascript program for the above approach// Function to find the maximum// and minimum number of elements// whose sum is less than equal// to Kfunction findMinMax(arr, N, K) { // Sorting both arrays arr.sort(); // To store the minimum and maximum // number of elements whose sum is // less than equal to K let maxNumEle = 0; let minNumEle = 0; // Store the cumulative sum let i, cumSum1 = 0; // Iterate in the range [0, N-1] for (i = 0; i < N; i++) { cumSum1 += arr[i]; // If cumSum1 is less than K if (cumSum1 <= K) maxNumEle += 1; else break; } // Store the cumulative sum let cumSum2 = 0; // Iterate in the range [N-1, 0] for (i = N - 1; i >= 0; i--) { cumSum2 += arr[i]; // If cumSum2 is less than K if (cumSum2 <= K) minNumEle += 1; else break; } // Print the value of maxNumEle and minNumEle document.write(maxNumEle + " " + minNumEle);}// Driver Code// Given Inputlet N = 4;let K = 7;let arr = [6, 2, 1, 3];// Function CallfindMinMax(arr, N, K);// This code is contributed by gfgking</script> |
Output
3 1
Time Complexity: O(NlogN)
Auxiliary Space: O(1)
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!
