Given an array of integers A of size N.

Value of Subset of array A is defined as the sum of squares all numbers in that subset.

Calculate and return the sum of values of all possible non-empty subset of array A modulo(10^9+7).

1 Like

I am not very sure but I think this problem can be done in O(N) using this approach-

We essentially count how many times an element can appear(that is it’s frequency) say it’s `f[i]`

for some element at index `i`

, say `arr[i]`

, using combinatorics, `f[i]`

for each`arr[ i]`

will be `2^(n-1)`

. So, all you need is the sum of `arr[i]^2 * 2^(n-1)`

over all `i`

and take the modulo by the mentioned number. Use the modulo sum property to avoid overflow.