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 eacharr[ 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.