CHARGED UP ARRAY**

QUESTION : -

N.B - This question was asked in Lenskart SDE-1 & SDE-2 hiring challenge and source is at CHARGED UP ARRAY.

You are given with an array A of size N . An element A_i is said to be charged if its value(A_i) is greater than or equal to K_i . K_i is the total number of subsets of array A, that consist of element A_i .

Total charge value of the array is defined as the summation of all charged elements present in the array mod 10⁹+7.

Your task is to output the total charge value of the given array A.

INPUT FORMAT:

The first line of input contains the number of test cases T.

The first line of each test case consists of N, the size of the array.

Next line contains N space-separated integers corresponding to each element A_i.

OUTPUT FORMAT:

For each test case, output a single number corresponding to total charge value of the given array.

CONSTRAINTS:

1 ≤ T ≤ 100

1 ≤ N ≤ 10⁵

0 ≤ A_i ≤ 10¹⁸

SAMPLE INPUT :

2

3

3 4 5

2

1 6

SAMPLE OUTPUT:

9

6

Explanation

CASE 1:

Possible subsets are: {3}, {4}, {5}, {3,4}, {3,5}, {4,5}, {3,4,5}, {}.

Element 3 is present in 4 subsets. As 3<4, it is not charged.

Element 4 is present in 4 subsets. As 4>=4, it is charged.

Element 5 is present in 4 subsets. As 5>=4, it is charged.

Total charge=4+5=9

CASE 2:

Possible subsets are: {1}, {6}, {1,6}, {}.

Element 1 is present in 2 subsets. As 1<2, it is not charged.

Element 6 is present in 2 subsets. As 6>=2, it is charged.

Total charge=6

Time Limit: 2.0 sec(s) for each input file.

Memory Limit: 256 MB

Source Limit: 1024 KB

Ans : -

I have a question for you, If a set A consists of n elements then how many subsets possible for that set? Obviously, if you have an elementary knowledge you will say 2ⁿ subsets in total.

Now let's apply the logic. What we have to do is, taking one element out of the set and check if it is charged. After taking one element out we are remaining with n-1 elements. So the total subset possible is 2^n-1 and we have one element in hand. Introducing that element in each subset of n-1 elements we get the same 2^n-1 subsets. Hence just we have to check if the number in hand is greater than 2^n-1 or not.

C++ Code:-

#include<bits/stdc++.h>

#define MOD 1000000007

using namespace std;

typedef long long int ll;

int main()

{

    ios_base::sync_with_stdio(false);

    cin.tie(NULL);

    int t;

    cin>>t;

    while(t--)

    {

        ll n;

        cin>>n;

        ll array[n];

        ll sum=0;

        for (ll i=0;i<n;i++)

        {

            cin>>array[i];

            if (array[i]>=(pow(2,n-1)))

            {

                sum=sum+array[i];

                sum=sum%MOD;

            }

        }

        cout<<sum<<endl;

    }

}

Hope that helps, please don't copy code, just take the reference :)