Given an array A[] containing N elements and an integer K. The task is to calculate the product of all elements of subsequences of size K except the minimum and the maximum elements for each subsequence.
Note: Since the answer can be very large so print the final answer as mod of 109 + 7.
Examples:
Input : arr[] = {1, 2, 3 4}, K = 3
Output : 36
Subsequences of length 3 are:
{1, 2, 3}, {1, 2, 4}, {1, 3, 4}, {2, 3, 4}
Excluding minimum and maximum elements from
each of the above subsequences, product will be:
(2 * 2 * 3 * 3) = 36.
Input : arr[] = {10, 5, 16, 6}, k=3
Output : 3600
Naive Approach: A simple approach is to generate all possible subsequences one by one and multiply all elements except maximum and minimum and further multiplying all of them. Since there will be a total of (n)C(K) subsequences all having K – 2 elements to be multiplied which is tedious work to do.
Efficient Approach: The idea is to first sort the array since it doesn’t matter if we consider subsequences or subsets.
Now count the occurrence of each element one by one.
In total, a number can occur in (n-1)C(K-1) subsequences out of which (i)C(K-1) times it will occur as maximum element and (n-i-1)C(K-1) times it will occur as a minimum element of that subsequence.
Hence, in total 
element will occur:
(n-1)C(K-1) - (i)C(K-1) - (n-i-1)C(K-1) times. (let's say it x)
So, at first we’ll be calculating x for each element a[i] and then multiply a[i] x times. i.e (![a[i]^x mod(10^9 + 7)](https://geeksforgeeks.org/wp-content/uploads/2023/11/dominic_rubhabha_quicklatex.com-8baa253819b7ac2e61ef1a77733df6bd_l3.png "Rendered by QuickLaTeX.com")
).
Since, It’s too difficult to calculate this for large arrays, so we’ll use Fermat’s Little Theorem.
Below is the implementation of the above approach:
C++
// C++ program to find product of all // Subsequences of size K except the // minimum and maximum Elements#include <bits/stdc++.h>using namespace std;#define MOD 1000000007#define ll long long#define max 101// 2D array to store value of // combinations nCrll C[max - 1][max - 1];ll power(ll x, unsigned ll y){ unsigned ll res = 1; x = x % MOD; while (y > 0) { if (y & 1) { res = (res * x) % MOD; } y = y >> 1; x = (x * x) % MOD; } return res % MOD;}// Function to pre-calculate value of all // combinations nCrvoid combi(int n, int k){ int i, j; for (i = 0; i <= n; i++) { for (j = 0; j <= min(i, k); j++) { if (j == 0 || j == i) C[i][j] = 1; else C[i][j] = (C[i - 1][j - 1] % MOD + C[i - 1][j] % MOD) % MOD; } }}// Function to calculate product of all subsequences // except the minimum and maximum elementsunsigned ll product(ll a[], int n, int k){ unsigned ll ans = 1; // Sorting array so that it becomes easy // to calculate the number of times an // element will come in first or last place sort(a, a + n); // An element will occur 'powa' times in total // of which 'powla' times it will be last element // and 'powfa' times it will be first element ll powa = C[n - 1][k - 1]; for (int i = 0; i < n; i++) { ll powla = C[i][k - 1]; ll powfa = C[n - i - 1][k - 1]; // In total it will come // powe = powa-powla-powfa times ll powe = ((powa % MOD) - (powla + powfa) % MOD + MOD) % MOD; // Multiplying a[i] powe times using // Fermat Little Theorem under MODulo // MOD for fast exponentiation unsigned ll mul = power(a[i], powe) % MOD; ans = ((ans % MOD) * (mul % MOD)) % MOD; } return ans % MOD;}// Driver Codeint main(){ // pre-calculation of all combinations combi(100, 100); ll arr[] = { 1, 2, 3, 4 }; int n = sizeof(arr) / sizeof arr[0]; int k = 3; unsigned ll ans = product(arr, n, k); cout << ans << endl; return 0;} |
Java
// Java program to find product of all // Subsequences of size K except the // minimum and maximum Elementsimport java.util.Arrays;class GFG { static int MOD= 1000000007;static int max =101;// 2D array to store value of // combinations nCrstatic long C[][] = new long[max ][max];static long power(long x, long y){ long res = 1; x = x % MOD; while (y > 0) { if (y % 2== 1) { res = (res * x) % MOD; } y = y >> 1; x = (x * x) % MOD; } return res % MOD;}// Function to pre-calculate value of all // combinations nCrstatic void combi(int n, int k){ int i, j; for (i = 0; i <= n; i++) { for (j = 0; j <= Math.min(i, k); j++) { if (j == 0 || j == i) C[i][j] = 1; else C[i][j] = (C[i - 1][j - 1] % MOD + C[i - 1][j] % MOD) % MOD; } }}// Function to calculate product of all subsequences // except the minimum and maximum elementsstatic long product(long a[], int n, int k){ long ans = 1; // Sorting array so that it becomes easy // to calculate the number of times an // element will come in first or last place Arrays.sort(a); // An element will occur 'powa' times in total // of which 'powla' times it will be last element // and 'powfa' times it will be first element long powa = C[n - 1][k - 1]; for (int i = 0; i < n; i++) { long powla = C[i][k - 1]; long powfa = C[n - i - 1][k - 1]; // In total it will come // powe = powa-powla-powfa times long powe = ((powa % MOD) - (powla + powfa) % MOD + MOD) % MOD; // Multiplying a[i] powe times using // Fermat Little Theorem under MODulo // MOD for fast exponentiation long mul = power(a[i], powe) % MOD; ans = ((ans % MOD) * (mul % MOD)) % MOD; } return ans % MOD;}// Driver Codepublic static void main(String[] args){ // pre-calculation of all combinations combi(100, 100); long arr[] = { 1, 2, 3, 4 }; int n = arr.length; int k = 3; long ans = product(arr, n, k); System.out.println(ans);}}/* This code contributed by PrinciRaj1992 */ |
Python3
# Python 3 program to find product of all # Subsequences of size K except the # minimum and maximum ElementsMOD = 1000000007max = 101# 2D array to store value of # combinations nCrC = [[0 for i in range(max)] for j in range(max)]def power(x,y): res = 1 x = x % MOD while (y > 0): if (y & 1): res = (res * x) % MOD y = y >> 1 x = (x * x) % MOD return res % MOD# Function to pre-calculate value of all # combinations nCrdef combi(n, k): for i in range(n + 1): for j in range(min(i, k) + 1): if (j == 0 or j == i): C[i][j] = 1 else: C[i][j] = (C[i - 1][j - 1] % MOD + C[i - 1][j] % MOD) % MOD# Function to calculate product of all subsequences # except the minimum and maximum elementsdef product(a, n, k): ans = 1 # Sorting array so that it becomes easy # to calculate the number of times an # element will come in first or last place a.sort(reverse = False) # An element will occur 'powa' times in total # of which 'powla' times it will be last element # and 'powfa' times it will be first element powa = C[n - 1][k - 1] for i in range(n): powla = C[i][k - 1] powfa = C[n - i - 1][k - 1] # In total it will come # powe = powa-powla-powfa times powe = ((powa % MOD) - (powla + powfa) % MOD + MOD) % MOD # Multiplying a[i] powe times using # Fermat Little Theorem under MODulo # MOD for fast exponentiation mul = power(a[i], powe) % MOD ans = ((ans % MOD) * (mul % MOD)) % MOD return ans % MOD# Driver Codeif __name__ == '__main__': # pre-calculation of all combinations combi(100, 100) arr = [1, 2, 3, 4] n = len(arr) k = 3 ans = product(arr, n, k) print(ans)# This code is contributed by# Surendra_Gangwar |
C#
// C# program to find product of all // Subsequences of size K except the // minimum and maximum Elementsusing System;class GFG{static int MOD = 1000000007;static int max = 101;// 2D array to store value of // combinations nCrstatic long [,]C = new long[max, max];static long power(long x, long y){ long res = 1; x = x % MOD; while (y > 0) { if (y % 2 == 1) { res = (res * x) % MOD; } y = y >> 1; x = (x * x) % MOD; } return res % MOD;}// Function to pre-calculate value // of all combinations nCrstatic void combi(int n, int k){ int i, j; for (i = 0; i <= n; i++) { for (j = 0; j <= Math.Min(i, k); j++) { if (j == 0 || j == i) C[i, j] = 1; else C[i, j] = (C[i - 1, j - 1] % MOD + C[i - 1, j] % MOD) % MOD; } }}// Function to calculate product of // all subsequences except // the minimum and maximum elementsstatic long product(long []a, int n, int k){ long ans = 1; // Sorting array so that it becomes easy // to calculate the number of times an // element will come in first or last place Array.Sort(a); // An element will occur 'powa' times // in total of which 'powla' times it // will be last element and 'powfa' times // it will be first element long powa = C[n - 1, k - 1]; for (int i = 0; i < n; i++) { long powla = C[i, k - 1]; long powfa = C[n - i - 1, k - 1]; // In total it will come // powe = powa-powla-powfa times long powe = ((powa % MOD) - (powla + powfa) % MOD + MOD) % MOD; // Multiplying a[i] powe times using // Fermat Little Theorem under MODulo // MOD for fast exponentiation long mul = power(a[i], powe) % MOD; ans = ((ans % MOD) * (mul % MOD)) % MOD; } return ans % MOD;}// Driver Codestatic public void Main (){ // pre-calculation of all combinations combi(100, 100); long []arr = { 1, 2, 3, 4 }; int n = arr.Length; int k = 3; long ans = product(arr, n, k); Console.WriteLine(ans);}}// This code contributed by ajit |
Javascript
<script> // Javascript program to find product of all // Subsequences of size K except the // minimum and maximum Elements let MOD= 1000000007; let max =101; // 2D array to store value of // combinations nCr let C = new Array(max); for(let i = 0; i < max; i++) { C[i] = new Array(max); for(let j = 0; j < max; j++) { C[i][j] = 0; } } function power(x, y) { let res = 1; x = x % MOD; while (y > 0) { if (y % 2== 1) { res = (res * x) % MOD; } y = y >> 1; x = (x * x) % MOD; } return res % MOD; } // Function to pre-calculate value of all // combinations nCr function combi(n, k) { let i, j; for (i = 0; i <= n; i++) { for (j = 0; j <= Math.min(i, k); j++) { if (j == 0 || j == i) C[i][j] = 1; else C[i][j] = (C[i - 1][j - 1] % MOD + C[i - 1][j] % MOD) % MOD; } } } // Function to calculate product of all subsequences // except the minimum and maximum elements function product(a, n, k) { let ans = 1; // Sorting array so that it becomes easy // to calculate the number of times an // element will come in first or last place a.sort(function(a, b){return a - b}); // An element will occur 'powa' times in total // of which 'powla' times it will be last element // and 'powfa' times it will be first element let powa = C[n - 1][k - 1]; for (let i = 0; i < n; i++) { let powla = C[i][k - 1]; let powfa = C[n - i - 1][k - 1]; // In total it will come // powe = powa-powla-powfa times let powe = ((powa % MOD) - (powla + powfa) % MOD + MOD) % MOD; // Multiplying a[i] powe times using // Fermat Little Theorem under MODulo // MOD for fast exponentiation let mul = power(a[i], powe) % MOD; ans = ((ans % MOD) * (mul % MOD)) % MOD; } return ans % MOD; } // pre-calculation of all combinations combi(100, 100); let arr = [ 1, 2, 3, 4 ]; let n = arr.length; let k = 3; let ans = product(arr, n, k); document.write(ans);</script> |
Output:
36
Time Complexity: O(nlogn + max*max), where n is the size of the given array and max is the defined constant.
Auxiliary Space: O(max*max), where max is the defined constant.
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!
