Given an array, arr[] of size N and an integer K, the task is to find the number of ways of selecting K array elements, such that the sum of these K elements is the maximum possible sum.
Examples:
Input: arr[] = {3, 1, 1, 2}, K = 3
Output: 2
Explanation:
The possible ways of selecting 3 elements are:
- {arr[0] (=3), arr[1] (=1), arr[2] (=1)}, the sum of the subset is equal to (3+1+1 = 5).
- {arr[0] (=3), arr[1] (=1), arr[3] (=2)}, the sum of the subset is equal to (3+1+2 = 6).
- {arr[0] (=3), arr[2] (=1), arr[3] (=2)}, the sum of the subset is equal to (3+1+2 = 6).
- {arr[1] (=1), arr[2] (=1), arr[3] (=2)}, the sum of the subset is equal to (1+1+2 = 4).
Therefore, the total number of ways of selecting the K element with the maximum sum(= 6) is equal to 2.
Input: arr[] = { 2, 3, 4, 5, 2, 2 }, K = 4
Output: 3Input: arr[]= {5, 4, 3, 3, 3, 3, 3, 1, 1}, K = 4
Output: 10
Approach: The problem can be solved by sorting the array in descending order. Follow the steps below to solve the problem:
- Sort the array in descending order.
- Calculate the number of times the Kth element, in the prefix of K-1 of the array, and then store it in a variable, say P.
- Calculate the number of times the Kth element in the array, and then store it in a variable, say Q.
- Finally, print the value of the number of ways of selecting, P element from the Q elements, i.e C(Q, P) 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 factorial of an// integerint fact(int n){ int res = 1; for (int i = 2; i <= n; i++) res = res * i; return res;}// Function to find the value of nCrint C(int n, int r){ return fact(n) / (fact(r) * fact(n - r));}// Function to find the number of ways// to select K elements with maximum// sumint findWays(int arr[], int N, int K){ // Sort the array in descending order sort(arr, arr + N, greater<int>()); // Stores the frequency of arr[K-1] // in the prefix of K-1 int p = 0; // Stores the frequency of arr[K-1] // in the array arr[] int q = 0; // Iterate over the range [0, K] for (int i = 0; i < K; i++) { // If arr[i] is equal to arr[K-1] if (arr[i] == arr[K - 1]) { p++; } } // Traverse the array arr[] for (int i = 0; i < N; i++) { // If arr[i] is equal to arr[K-1] if (arr[i] == arr[K - 1]) { q += 1; } } // Stores the number of ways of // selecting p from q elements int ans = C(q, p); // Return ans return ans;}// Driver Codeint main(){ // Input int arr[] = { 2, 3, 4, 5, 2, 2 }; int N = sizeof(arr) / sizeof(arr[0]); int K = 4; // Function call cout << findWays(arr, N, K); return 0;} |
Java
// Java program for the above approachimport java.util.*;class GFG{// Function to find the factorial of an// integerstatic int fact(int n){ int res = 1; for (int i = 2; i <= n; i++) res = res * i; return res;}// Function to find the value of nCrstatic int C(int n, int r){ return fact(n) / (fact(r) * fact(n - r));}// Function to find the number of ways// to select K elements with maximum// sumstatic int findWays(Integer arr[], int N, int K){ // Sort the array in descending order Arrays.sort(arr, Collections.reverseOrder()); // Stores the frequency of arr[K-1] // in the prefix of K-1 int p = 0; // Stores the frequency of arr[K-1] // in the array arr[] int q = 0; // Iterate over the range [0, K] for (int i = 0; i < K; i++) { // If arr[i] is equal to arr[K-1] if (arr[i] == arr[K - 1]) { p++; } } // Traverse the array arr[] for (int i = 0; i < N; i++) { // If arr[i] is equal to arr[K-1] if (arr[i] == arr[K - 1]) { q += 1; } } // Stores the number of ways of // selecting p from q elements int ans = C(q, p); // Return ans return ans;}// Driver Codepublic static void main(String[] args){ // Input Integer arr[] = { 2, 3, 4, 5, 2, 2 }; int N = arr.length; int K = 4; // Function call System.out.print(findWays(arr, N, K));}}// This code is contributed by shikhasingrajput |
Python3
# Python for the above approach# Function to find the factorial of an# integerdef fact(n): res = 1 for i in range(2, n + 1): res = res * i return res# Function to find the value of nCrdef C(n, r): return fact(n) / (fact(r) * fact(n - r))# Function to find the number of ways# to select K elements with maximum# sumdef findWays(arr, N, K): # Sort the array in descending order arr.sort(reverse=True) # Stores the frequency of arr[K-1] # in the prefix of K-1 p = 0 # Stores the frequency of arr[K-1] # in the array arr[] q = 0 # Iterate over the range [0, K] for i in range(K): # If arr[i] is equal to arr[K-1] if (arr[i] == arr[K - 1]): p += 1 # Traverse the array arr[] for i in range(N): # If arr[i] is equal to arr[K-1] if (arr[i] == arr[K - 1]): q += 1 # Stores the number of ways of # selecting p from q elements ans = C(q, p) # Return ans return int(ans)# Driver Code# Inputarr = [2, 3, 4, 5, 2, 2]N = len(arr)K = 4# Function callprint(findWays(arr, N, K))# This code is contributed by gfgking. |
C#
// C# program for the above approachusing System;class Program{ // Function to find the factorial of an// integerstatic int fact(int n){ int res = 1; for(int i = 2; i <= n; i++) res = res * i; return res;}// Function to find the value of nCrstatic int C(int n, int r){ return fact(n) / (fact(r) * fact(n - r));}// Function to find the number of ways// to select K elements with maximum// sumstatic int findWays(int []arr, int N, int K){ // Sort the array in descending order Array.Sort(arr); Array.Reverse(arr); // Stores the frequency of arr[K-1] // in the prefix of K-1 int p = 0; // Stores the frequency of arr[K-1] // in the array arr[] int q = 0; // Iterate over the range [0, K] for(int i = 0; i < K; i++) { // If arr[i] is equal to arr[K-1] if (arr[i] == arr[K - 1]) { p++; } } // Traverse the array arr[] for(int i = 0; i < N; i++) { // If arr[i] is equal to arr[K-1] if (arr[i] == arr[K - 1]) { q += 1; } } // Stores the number of ways of // selecting p from q elements int ans = C(q, p); // Return ans return ans;}// Driver codestatic void Main(){ int []arr = { 2, 3, 4, 5, 2, 2 }; int N = arr.Length; int K = 4; // Function call Console.Write(findWays(arr, N, K));}}// This code is contributed by SoumikMondal |
Javascript
<script>// JavaScript program for the above approach// Function to find the factorial of an// integerfunction fact(n) { let res = 1; for (let i = 2; i <= n; i++) res = res * i; return res;}// Function to find the value of nCrfunction C(n, r) { return fact(n) / (fact(r) * fact(n - r));}// Function to find the number of ways// to select K elements with maximum// sumfunction findWays(arr, N, K){ // Sort the array in descending order arr.sort(function (a, b){ return b - a; }); // Stores the frequency of arr[K-1] // in the prefix of K-1 let p = 0; // Stores the frequency of arr[K-1] // in the array arr[] let q = 0; // Iterate over the range [0, K] for(let i = 0; i < K; i++) { // If arr[i] is equal to arr[K-1] if (arr[i] == arr[K - 1]) { p++; } } // Traverse the array arr[] for(let i = 0; i < N; i++) { // If arr[i] is equal to arr[K-1] if (arr[i] == arr[K - 1]) { q += 1; } } // Stores the number of ways of // selecting p from q elements let ans = C(q, p); // Return ans return ans;}// Driver Code// Inputlet arr = [ 2, 3, 4, 5, 2, 2 ];let N = arr.length;let K = 4;// Function calldocument.write(findWays(arr, N, K));// This code is contributed by Potta Lokesh</script> |
Output
3
Time Complexity: O(N*log(N) + K)
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!
