Last Updated: 23 Apr, 2021
Expanse Of Subsequences
Hard
Asked in company
You are given an array/list ‘ARR’ consisting of ‘N’ positive integers.
For any sequence ‘S’, let the expanse of ‘S’ be the difference between the maximum and the minimum element of ‘S’.
Your task is to return the sum of the expanse of all non-empty subsequences of ‘ARR’. Return this sum in modulo 10^9 + 7.
Note :
Expanse of a sequence of length 1 is always 0.
Input Format :
The first line contains a single integer ‘T’ representing the number of test cases. The 'T' test cases follow.
The first line of each test case will contain a single integer ‘N’, representing the size of ‘ARR’
The second line of each test case will contain ‘N’ space-separated integers representing array/list ‘ARR’.
Output Format :
For each test case, print a single integer that represents the sum of the expanse of all subsequences in modulo 10^9+7.
Output for every test case will be printed in a separate line.
Note :
You don’t need to print anything, It has already been taken care of. Just implement the given function.
Constraints :
1 <= T <= 50
2 <= N <= 10000
1 <= ARR[i] <= 10^9
Where 'ARR[i]' denotes the 'ith' element of the array.
Time limit: 1 sec
Approaches
The basic idea is to initialize an integer variable ‘RESULT’: = 0, then we one by one find each subsequence of ‘ARR’ using bit masking and for each subsequence, we add the difference of its maximum and minimum element to ‘RESULT’. Note we do modulo 10^9 + 7 in addition.
The steps are as follows:
- Initialize an integer variable ‘RESULT’:= 0.
- Run a loop where ‘MASK’ ranges from 1 to 2^N-1 and for each ‘i’ do the following -:
- Initialize two integer variables ‘MAXELE’: = 0, ‘MINELE’:= INF.
- Run a loop where ‘i’ ranges from 0 to N-1 and do the following -:
- If the ith bit is set in ‘MASK’.
- Do ‘MAXELE’ = max(‘MAXELE’, ARR[i]).
- Do ‘MINELE’ = min(‘MINELE’, ARR[i]).
- If the ith bit is set in ‘MASK’.
- Do RESULT: = (RESULT + ‘MAXELE’ - ‘MINELE’) % (10^9+7).
- Return ‘RESULT’.
The basic idea is to sort the array in non-decreasing order. Then for any two indices ‘i’, ‘j’ (‘i’ < ‘j’) number of subsequences having ARR[i] as a minimum element and ARR[j] as the maximum number will be 2^(j-i-1).
We initialize an integer variable ‘RESULT’: = 0, and for each pair of indices (‘i’, ‘j’) such that ‘j’ > ‘i’, we add (ARR[j] - ARR[i]) * 2^(j-i-1) in ‘RESULT’ (in modulo 10^9+7 ). To optimize it further we precompute power of 2 up to ‘N’ in modulo 10^9+7.
The steps are as follows:
- Make an array/list ‘POWER’ of size ‘N’ and fill it by 1.
- Run a loop where ‘i’ ranges from 1 to ‘N’-1, and for each ‘i’ do POWER[i] = (POWER[i-1] * 2) % (10^9+7).
- Initialize an integer variable ‘RESULT’:= 0.
- Sort ‘ARR’ in non-decreasing order.
- Run a loop where ‘i’ ranges from 0 to ‘N’-1 and do the following -:
- Run a loop where ‘j’ ranges from ‘i’+1’ to ‘N’-1 and do the following -
- Do RESULT = RESULT + POWER[j-i-1] * (ARR[j] - ARR[i]), Note you should perform these arithmetic operations in modulo 10^9+7.
- Run a loop where ‘j’ ranges from ‘i’+1’ to ‘N’-1 and do the following -
- Return ‘RESULT’.
As discussed in the previous approach, we need to find the sum of (ARR[j] - ARR[i]) * 2^(j-i-1) for each pair (i, j) such that ‘j’ > ‘i’. From this we can observe that for any indices ‘i’, we add ARR[i] * 2^(j-i-1) if 0 <= j < i and we subtract ARR[i] * 2^(j-i+1) if ‘N’ > j > i.
For any integer ‘i’, summation of 2^(j-i+1) for all 0 <= j < i, is 2^i -1 and summation of 2^(j-i+1) for all N > j > i is 2^(N-i-1) -1. Thus for each index ‘i’ we should add ARR[i] * (2^i - 2^(N-i-1)) in the final result.
The steps are as follows:
- Make an array/list ‘POWER’ of size ‘N’ and fill it by 1.
- Run a loop where ‘i’ ranges from 1 to ‘N’-1, and for each ‘i’ do POWER[i] = (POWER[i-1] * 2) % (10^9+7).
- Initialize an integer variable ‘RESULT’:= 0.
- Sort ‘ARR’ in non-decreasing order.
- Run a loop where ‘i’ ranges from 0 to ‘N’-1 and do the following -:
- Do RESULT = RESULT + ARR[i] * (POWER[i] - POWER[N-i-1]), Note you should perform these arithmetic operations in modulo 10^9+7.
- Return ‘RESULT’.
Similar problems