Expanse Of Subsequences

Hard
0/120
Average time to solve is 45m
profile
Contributed by
7 upvotes
Asked in company
Apple

Problem statement

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.
Detailed explanation ( Input/output format, Notes, Images )

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

Sample Input 1 :

2
3
2 1 3
1
1

Sample Output 1 :

6
0
Explanation of sample input 1 :
In the first test case, subsequences are [1], [2], [3], [2, 1], [2, 3], [1, 3], and [2, 1, 3].
The corresponding expanse are 0, 0, 0, 1, 1, 2, 2.
The sum of these expanse is 0 + 0 + 0 + 1 + 1 + 2 + 2 = 6.

In the second test case, there is only one subsequence [1], and its expanse is 0.

Sample Input 2 :

2
5
2 2 2 2 2
2
1 2

Sample Output 2 :

0
1
Hint

Find expanse for each non-empty subsequence of ‘ARR’.

Approaches (3)
Brute Force

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:

  1. Initialize an integer variable ‘RESULT’:= 0.
  2. Run a loop where ‘MASK’ ranges from 1 to 2^N-1 and for each ‘i’ do the following -:
    1. Initialize two integer variables ‘MAXELE’: = 0,  ‘MINELE’:= INF.
    2. Run a loop where ‘i’ ranges from 0 to N-1 and do the following -:
      1. If the ith bit is set in ‘MASK’.
        1. Do ‘MAXELE’ = max(‘MAXELE’, ARR[i]).
        2. Do ‘MINELE’ = min(‘MINELE’, ARR[i]).
    3. Do RESULT: = (RESULT + ‘MAXELE’ - ‘MINELE’) % (10^9+7).
  3. Return ‘RESULT’.
Time Complexity

O(N * (2^N)), where 'N' is the size of ‘ARR’.

 

The number of subsequences is of order O(2^N) and for each of these subsequences, we find minimum and maximum elements which take times of the order of O(N). Thus, the overall time complexity will be O(N * (2^N)). 

Space Complexity

O(1)

 

We are using constant extra space here.

Code Solution
(100% EXP penalty)
Expanse Of Subsequences
Full screen
Console