Count of ways to choose K elements from given Array with maximum sum

0 0 7 minutes read

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: 3

Input: 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 K^th 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 K^th 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
// integer
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 nCr
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
// sum
int 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 Code
int 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 approach
 
import java.util.*;
 
class GFG{
 
// Function to find the factorial of an
// integer
static 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 nCr
static 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
// sum
static 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 Code
public 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
# integer
def fact(n):
    res = 1
    for i in range(2, n + 1):
        res = res * i
 
    return res
 
# Function to find the value of nCr
def C(n, r):
    return fact(n) / (fact(r) * fact(n - r))
 
# Function to find the number of ways
# to select K elements with maximum
# sum
def 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
 
 
# Input
arr = [2, 3, 4, 5, 2, 2]
N = len(arr)
K = 4
 
# Function call
print(findWays(arr, N, K))
 
# This code is contributed by gfgking.

C#

// C# program for the above approach
using System;
 
class Program{
     
// Function to find the factorial of an
// integer
static 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 nCr
static 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
// sum
static 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 code
static 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
// integer
function fact(n) 
{
    let res = 1;
    for (let i = 2; i <= n; i++)
        res = res * i;
         
    return res;
}
 
// Function to find the value of nCr
function C(n, r) 
{
    return fact(n) / (fact(r) * fact(n - r));
}
 
// Function to find the number of ways
// to select K elements with maximum
// sum
function 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
 
// Input
let arr = [ 2, 3, 4, 5, 2, 2 ];
let N = arr.length;
let K = 4;
 
// Function call
document.write(findWays(arr, N, K));
 
// This code is contributed by Potta Lokesh
 
</script>

Output

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 zambiatek!