Product of all Subsequences of size K except the minimum and maximum Elements in C++

Given an array arr[n], containing n number of integers and an integer k for defining the size; the task is to print the product of all the subsequences of size k except the minimum and maximum elements.

Let us assume we have a set of 4 elements {1, 2, 3, 4} and k as 2 so its subsets will be − {1, 2}, {2, 3}, {3, 4}, {1, 4}, {1, 3}, {2, 4}

So excluding the maximum element 4, and minimum element 1, the remaining elements will be −

2, 3, 3, 3, 2, product of which will be −

2 * 3 * 3 * 3 * 2 = 108

Likewise we have to solve the problem

Example

Input: arr[] = {3, 4, 1, 7}, k = 3 Output: 144 Explanation: subset will be, {3, 4, 1}, {4, 1, 7}, {3, 1, 7}, {3, 4, 7} Eliminating maximum value 7 and minimum 1 we will get: {3, 4}, {4}, {3}, {3, 4}, so multiplying these will give us: 3 * 4 * 4 * 3 = 144 Input: arr[] = {1, 2, 3, 4}, k = 3 Output: 36

Approach we are using to solve the above problem −

There can be many ways to achieve the solution. There is one approach in which we can generate all the possible subsequences one by one, and product all the elements except the maximum and the minimum of the set. Although this approach is easy to achieve but have very high complexity and the approach is inefficient.

We have an efficient approach also, in this approach we will firstly sort an array, disregarding the subsets or subsequents to be considered or not.

Then we will count the number of occurence of each element one by one.

A number can occur C(k-1) (n-1)subsequences out of which the C(k-1) (i)times we will occur maximum element C(k-1) (n-i-1) times it will occur as minimum element of that subsequence.

Hence, we can state that this is more efficient approach as the ith element will occur −

C(k-1) (n-1)- C(k-1) (i)- C(k-1) (n-i-1) times.

Now, first we will solve x for each element in arr[i], so the answer of it can be really difficult to calculate so we can use Fermat’s Little Theorem.

Note −Since the answer can be really large so we will print the answer in mod of 109+7.

Algorithm

Start Step 1-> Declare function to calculate the pairs combination    void pairs(int a, int b)    Declare int i, j    Loop For i = 0 and i <= a and i++       Loop For j = 0 and j <= min(i, b) and j++          IF (j == 0 || j == i)             Set c[i][j] = 1          End          Else             Set c[i][j] = (c[i - 1][j - 1] % val + c[i - 1][j] % val) % val          End       End    End Step 2-> declare function for power    LL power(LL x, unsigned LL y)    Declare unsigned LL temp = 1    Set x = x % val    Loop While (y > 0)       IF(y & 1)          Set temp = (temp * x) % val       End       Set y = y >> 1       Set x = (x * x) % val    End    return temp % val Step 3-> Declare function to calculate product of all subsequences    unsigned LL product(LL arr[], int size, int k)    Declare and set unsigned LL temp = 1    Call function to sort an array as sort(arr, arr + size)    Declare and set as LL pow = c[size - 1][k - 1]    Loop For i = 0 and i < size and i++       Declare and set LL pow_l = c[i][k - 1]       Declare and set LL pow_f = c[size - i - 1][k - 1]       Declare and set LL pow_e = ((pow % val) - (pow_l + pow_f) % val + val) % val       Declare and set unsigned LL mul = power(arr[i], pow_e) % val       Set temp = ((temp % val) * (mul % val)) % val    End    return temp % val Step 4-> In main()    Call pairs(100, 100)    Declare and set LL arr[] = { 3, 4, 1, 7 }    Calculate size as int size = sizeof(arr) / sizeof arr[0]    Declare and set int k = 3    Declare and set unsigned LL temp = product(arr, size, k)    Print temp Stop

Example

 Live Demo

#include <bits/stdc++.h> using namespace std; #define val 1000000007 #define LL long long #define max 101 LL c[max - 1][max - 1]; LL power(LL x, unsigned LL y) {    unsigned LL temp = 1;    x = x % val;    while (y > 0) {       if (y & 1) {          temp = (temp * x) % val;       }       y = y >> 1;       x = (x * x) % val;    }    return temp % val; } void pairs(int a, int b) {    int i, j;    for (i = 0; i <= a; i++) {       for (j = 0; j <= min(i, b); j++) {          if (j == 0 || j == i)             c[i][j] = 1;          else             c[i][j] = (c[i - 1][j - 1] % val + c[i - 1][j] % val) % val;       }    } } //function to calculate product of all subsequences unsigned LL product(LL arr[], int size, int k) {    unsigned LL temp = 1;    //sorting array    sort(arr, arr + size);    LL pow = c[size - 1][k - 1];    for (int i = 0; i < size; i++) {       LL pow_l = c[i][k - 1];       LL pow_f = c[size - i - 1][k - 1];       LL pow_e = ((pow % val) - (pow_l + pow_f) % val + val) % val;       unsigned LL mul = power(arr[i], pow_e) % val;       temp = ((temp % val) * (mul % val)) % val;    }    return temp % val; } int main() {    // sum of all the pairs    pairs(100, 100);    LL arr[] = { 3, 4, 1, 7 };    int size = sizeof(arr) / sizeof arr[0];    int k = 3;    unsigned LL temp = product(arr, size, k);    cout<<"product of all subsequences of size k except minimum and maximum element is :"<<temp << endl;    return 0; }

Output

product of all subsequences of size k except minimum and maximum element is :144