Sum of Squares ( Codersbit InterviewBit )

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.