Recuento de formas de elegir K elementos de una array dada con suma máxima

Dada una array , arr[] de tamaño N y un entero K , la tarea es encontrar el número de formas de seleccionar K elementos de la array, de modo que la suma de estos K elementos sea la suma máxima posible.

Ejemplos:

Entrada: arr[] = {3, 1, 1, 2}, K = 3 
Salida: 2
Explicación: 
Las posibles formas de seleccionar 3 elementos son:

1. {arr[0] (=3), arr[1] (=1), arr[2] (=1)}, la suma del subconjunto es igual a (3+1+1 = 5).
2. {arr[0] (=3), arr[1] (=1), arr[3] (=2)}, la suma del subconjunto es igual a (3+1+2 = 6).
3. {arr[0] (=3), arr[2] (=1), arr[3] (=2)}, la suma del subconjunto es igual a (3+1+2 = 6).
4. {arr[1] (=1), arr[2] (=1), arr[3] (=2)}, la suma del subconjunto es igual a (1+1+2 = 4).

Por lo tanto, el número total de formas de seleccionar el elemento K con la suma máxima (= 6) es igual a 2.

Entrada: arr[] = { 2, 3, 4, 5, 2, 2 }, K = 4
Salida: 3

Entrada: arr[]= {5, 4, 3, 3, 3, 3, 3, 1, 1}, K = 4
Salida: 10

Enfoque: el problema se puede resolver ordenando la array en orden descendente . Siga los pasos a continuación para resolver el problema:  

• Ordene la array en orden descendente.
• Calcule el número de veces que el K ^-ésimo elemento, en el prefijo K-1 de la array, y luego guárdelo en una variable, digamos P.
• Calcule la cantidad de veces que el K ^-ésimo elemento en la array y luego guárdelo en una variable, digamos Q.
• Finalmente, imprima el valor del número de formas de seleccionar el elemento P de los elementos Q , es decir, C(Q, P) como respuesta.

A continuación se muestra la implementación del enfoque anterior:

// 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 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

# 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# 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

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

3

Complejidad de tiempo: O(N*log(N) + K)
Espacio auxiliar: O(1)