Subsequence Product

Hard
0/120
Average time to solve is 30m
2 upvotes
Asked in companies
OracleIntuitMicrosoft

Problem statement

Ninja recently studied about subsequences and his teacher gave him the following challenge which no other student was able to solve till now.

You are given an array ‘A’ of size ‘N’ and an integer ‘K’. You find all the subsequences of size ‘K’ from the array ‘A’. Now for each of the subsequences, you calculate the product of all elements except the minimum element and the maximum element of the subsequence. After that you need to calculate the product of all these values.

Output the final product calculated by Ninja. Since the answer can be large, output it modulo 10^9+7.

Example : 
N = 4 , K = 3
A = [ 1, 2, 3, 4 ]


Explanation : 

All subsequence of size ‘3’ are : 
[ 1, 2, 3 ]  : The product is 2.
[ 1, 2, 4 ]  : The product is 2.
[ 1, 3, 4 ]  : The product is 3.
[ 2, 3, 4 ]  : The product is 3.

The final product is 2*2*3*3 = 36.
Detailed explanation ( Input/output format, Notes, Images )
Input Format : 
The first line contains an integer 'T' which denotes the number of test cases to be run. Then the test cases follow.

The first line of each test case contains integers ‘N’ and ‘K’.

The next line contains ‘N’ integers representing the elements of array ‘A’.
Output format : 
For each test case, output an integer denoting the required product modulo 10^9+7.

Print the output of each test case in a new line.
Note : 
You don’t need to print anything. It has already been taken care of. Just implement the given function.
Constraints : 
1 <= T <= 10
3 <= N <= 5000
3 <= K <= N
1 <= A[i] <= 10^5

Time Limit : 1 sec
Sample Input 1 :
2
5 4
1 3 5 2 2
3 3
3 2 4
Sample Output 1 :
3456
3
Explanation Of Sample Input 1 :
For test case 1 we have,    

The subsequences are : 

[ 1, 3, 5, 2 ] with product 6.
[ 1, 3, 5, 2 ] with product 6.
[ 1, 3, 2, 2 ] with product 4.
[ 1, 5, 2, 2 ] with product 4.
[ 3, 5, 2, 2 ] with product 6.

Hence, the required product is 6*6*4*4*6 = 3456.

 For test case 2 we have,    

There is only 1 subsequence : 

[ 3, 2, 4 ] with product 3.

Hence, we output 3.
Sample Input 2 :
2
4 3
6 5 2 6 
5 3
9 7 4 2 10
Sample Output 2 :
900
8192
Hint

Think about the contribution of each element in the final result.

 

Approaches (1)
Optimal Approach

 

Approach : 

 

  • Since we are interested in subsequences, the order of elements doesn’t matter.
  • So, we first sort the array ‘A’.
  • Now, we observe that some element ‘A[i]’ will occur in ‘N-1CK-1’ subsequences.
    • This is because we have fixed the current element at index ‘i’ and we can choose ‘K-1’ more elements from the ‘N-1’ left elements.
  • Now, in some subsequences, this element can be a maximum element and in some it can be a minimum element. So, we need to subtract both these cases.
  • This element will be a maximum only if all other elements are chosen before index ‘i’.
  • So, there are ‘i-1CK-1’ such subsequences.
  • This element will be a minimum only if all other elements are chosen after index ‘i’.
  • So, there are ‘N-iCK-1’ such subsequences.
  • So, the total number of times an element at index ‘i’ will be contributing to the final answer is : ‘T’ = ‘N-1CK-1 - i-1CK-1 - N-iCK-1’.
  • So, we need to calculate ‘A[i]’ raised to ‘T’.
  • We will use Fermat’s Theorem for calculating this.
  • a^(p-1) = 1 mod p.
  • So, we can say that a^T = a^(T % (p-1) ) mod p.
  • So, first we need to calculate the value of ‘T%(p-1)’.
  • But since ‘p-1’ is not prime, we will calculate ‘NCr’ using recurrent formula :
  • N C r = ( N-1 C r ) + ( N-1 C r-1 ).
  • After calculating x = T%(p-1) , we calculate ‘(A[i]^x) mod p’ for each ‘A[i]’.
  • We multiply this value with our final answer.


 

Algorithm : 

 

  • Initialise a variable ‘ans’ = 1.
  • Initialise a constant ‘M’ = 10^9 + 7.
  • Calculate the value of ‘NCr’ for all ‘N<=5000’ and ‘r<=N’ and store in ‘C[i][j]’.
  • Sort the array ‘A’.
  • Run a loop from ‘i=0’ to ‘i=N-1’.
    • Calculate ‘tot’ = ‘C[N-1][K-1]’.
    • Calculate ‘maxi’ = ‘C[i][K-1]’.
    • Calculate ‘mini’ = ‘C[N-i-1][K-1]’.
    • Calculate ‘contr’ = ‘tot - maxi - mini’ % (M-1).
    • Calculate ‘ans’ = ‘ans * power ( A[i], contr )’ % M using extended Euclid Algorithm.
  • Return ‘ans’ as the final result.

 

Time Complexity

O( N^2 ) , where ‘N’ is the size of the array ‘A’.
 

We are calculating all binomial coefficients , so the overall time complexity is O( N^2 ).

 

Space Complexity

O( N^2 ) , where ‘N’ is the size of the array ‘A’.

 

We are storing all binomial coefficients , so the overall space complexity is O( N^2 ).

 

Code Solution
(100% EXP penalty)
Subsequence Product
Full screen
Console