Given an array arr[] of size N and an integer K, the task is to find the number of K length subsequences of this array such that the sum of these subsequences is the minimum possible.
Examples:
Input: arr[] = {1, 2, 3, 4}, K = 2
Output: 1
Subsequences of length 2 are (1, 2), (1, 3), (1, 4),
(2, 3), (2, 4) and (3, 4).
The minimum sum is 3 and the only subsequence
with this sum is (1, 2).Input: arr[] = {2, 1, 2, 2, 2, 1}, K = 3
Output: 4
Approach: The minimum possible sum of a subsequence of length K from the given array is the sum of the K smallest elements of the array. Let X be the maximum element among the K smallest elements of the array, and let the number of times it occurs among the K, the smallest elements of the array, be Y, and, its total occurrence, in the complete array, be cntX. Now, there are cntXCY ways to select this element, in the K smallest elements, which is the count of required subsequences.
Below is the implementation of the above approach:
C++
// C++ implementation of the approach#include <bits/stdc++.h>using namespace std;// Function to return the value of// Binomial Coefficient C(n, k)int binomialCoeff(int n, int k){ int C[n + 1][k + 1]; int i, j; // Calculate value of Binomial Coefficient // in bottom up manner for (i = 0; i <= n; i++) { for (j = 0; j <= min(i, k); j++) { // Base Cases if (j == 0 || j == i) C[i][j] = 1; // Calculate value using previously // stored values else C[i][j] = C[i - 1][j - 1] + C[i - 1][j]; } } return C[n][k];}// Function to return the count// of valid subsequencesint cntSubSeq(int arr[], int n, int k){ // Sort the array sort(arr, arr + n); // Maximum among the minimum K elements int num = arr[k - 1]; // Y will store the frequency of num // in the minimum K elements int Y = 0; for (int i = k - 1; i >= 0; i--) { if (arr[i] == num) Y++; } // cntX will store the frequency of // num in the complete array int cntX = Y; for (int i = k; i < n; i++) { if (arr[i] == num) cntX++; } return binomialCoeff(cntX, Y);}// Driver codeint main(){ int arr[] = { 1, 2, 3, 4 }; int n = sizeof(arr) / sizeof(int); int k = 2; cout << cntSubSeq(arr, n, k); return 0;} |
Java
// Java implementation of the approach import java.util.*;class GFG{ // Function to return the value of // Binomial Coefficient C(n, k) static int binomialCoeff(int n, int k) { int C[][] = new int [n + 1][k + 1]; int i, j; // Calculate value of Binomial Coefficient // in bottom up manner for (i = 0; i <= n; i++) { for (j = 0; j <= Math.min(i, k); j++) { // Base Cases if (j == 0 || j == i) C[i][j] = 1; // Calculate value using previously // stored values else C[i][j] = C[i - 1][j - 1] + C[i - 1][j]; } } return C[n][k]; } // Function to return the count // of valid subsequences static int cntSubSeq(int arr[], int n, int k) { // Sort the array Arrays.sort(arr); // Maximum among the minimum K elements int num = arr[k - 1]; // Y will store the frequency of num // in the minimum K elements int Y = 0; for (int i = k - 1; i >= 0; i--) { if (arr[i] == num) Y++; } // cntX will store the frequency of // num in the complete array int cntX = Y; for (int i = k; i < n; i++) { if (arr[i] == num) cntX++; } return binomialCoeff(cntX, Y); } // Driver code public static void main (String[] args) { int arr[] = { 1, 2, 3, 4 }; int n = arr.length; int k = 2; System.out.println(cntSubSeq(arr, n, k)); } }// This code is contributed by AnkitRai01 |
C#
// C# implementation of the approach using System; class GFG{ // Function to return the value of // Binomial Coefficient C(n, k) static int binomialCoeff(int n, int k) { int [,]C = new int [n + 1, k + 1]; int i, j; // Calculate value of Binomial Coefficient // in bottom up manner for (i = 0; i <= n; i++) { for (j = 0; j <= Math.Min(i, k); j++) { // Base Cases if (j == 0 || j == i) C[i, j] = 1; // Calculate value using previously // stored values else C[i, j] = C[i - 1, j - 1] + C[i - 1, j]; } } return C[n, k]; } // Function to return the count // of valid subsequences static int cntSubSeq(int []arr, int n, int k) { // Sort the array Array.Sort(arr); // Maximum among the minimum K elements int num = arr[k - 1]; // Y will store the frequency of num // in the minimum K elements int Y = 0; for (int i = k - 1; i >= 0; i--) { if (arr[i] == num) Y++; } // cntX will store the frequency of // num in the complete array int cntX = Y; for (int i = k; i < n; i++) { if (arr[i] == num) cntX++; } return binomialCoeff(cntX, Y); } // Driver code public static void Main (String[] args) { int []arr = { 1, 2, 3, 4 }; int n = arr.Length; int k = 2; Console.WriteLine(cntSubSeq(arr, n, k)); } }// This code is contributed by 29AjayKumar |
Python3
# Python3 implementation of the approach# Function to return the value of# Binomial Coefficient C(n, k)def binomialCoeff(n, k) : C = [[0 for i in range(n + 1)] for j in range(k + 1)] # Calculate value of Binomial Coefficient # in bottom up manner for i in range (0, n + 1 ): for j in range (0, min(i, k) + 1): # Base Cases if (j == 0 or j == i): C[i][j] = 1 # Calculate value using previously # stored values else : C[i][j] = C[i - 1][j - 1] + C[i - 1][j] return C[n][k]# Function to return the count# of valid subsequencesdef cntSubSeq(arr, n, k) : # Sort the array arr.sort() # Maximum among the minimum K elements num = arr[k - 1]; # Y will store the frequency of num # in the minimum K elements Y = 0; for i in range (k - 1, -1, 1) : if (arr[i] == num): Y += 1 # cntX will store the frequency of # num in the complete array cntX = Y; for i in range (k, n): if (arr[i] == num) : cntX += 1 return binomialCoeff(cntX, Y)# Driver codearr = [ 1, 2, 3, 4 ]n = len(arr)k = 2print(cntSubSeq(arr, n, k))# This code is contributed by ihritik |
Javascript
<script>// Javascript implementation of the// above approach// Function for the binomial coefficientfunction binomialCoeff(n, k){ var C = new Array(n + 1); // Loop to create 2D array using 1D array for (var i = 0; i < C.length; i++) { C[i] = new Array(k + 1); } var i, j; // Calculate value of Binomial Coefficient // in bottom up manner for (i = 0; i <= n; i++) { for (j = 0; j <= Math.min(i, k); j++) { // Base Cases if (j == 0 || j == i) C[i][j] = 1; // Calculate value using previously // stored values else C[i][j] = C[i - 1][j - 1] + C[i - 1][j]; } } return C[n][k];} // Function to return the count// of valid subsequencesfunction cntSubSeq(arr, n, k){ // Sort the array arr.sort(); // Maximum among the minimum K elements var num = arr[k - 1]; // Y will store the frequency of num // in the minimum K elements var Y = 0; for (var i = k - 1; i >= 0; i--) { if (arr[i] == num) Y+=1; } // cntX will store the frequency of // num in the complete array var cntX = Y; for (var i = k; i < n; i++) { if (arr[i] == num) cntX+=1; } return binomialCoeff(cntX, Y);}// Driver codevar arr = [ 1, 2, 3, 4 ];var n = arr.length;var k = 2;document.write(cntSubSeq(arr, n, k));// This code is contributed by ShubhamSingh10</script> |
Output:
1
Time Complexity: o(n2)
Auxiliary Space: O(n * k)
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!
