Problem statement

https://leetcode.com/problems/sum-of-subsequence-widths/

Solution

The will be $2^n$ subsequences, so there is no way we can directly check all of them. Instead, let us sort numbers and try to understand how many times each of them will be in final sum. Let us look at a1 <= a2 <= a3 <= a4 case. How many times a1 will be here? It will be 2^3 times as maximum and 2^0 times as minimum. a2 will be 2^2 times as maximum and 2^1 times as minimum. a3 will be 2^1 times as maximum and 2^2 times as minimum and finally a4 will be 2^0 times as maximum and 2^3 times as minimum. So, for this case we can say that answer is 7a1 + 2a2 - 2a3 - 7a4. Exactly the same logic can be used for n numbers, but we need to calculate coefficients modulo 10^9 + 7.

Complexity

Time complexity will be O(n log n): to sort numbers and smaller O(n) to calculate linear combination. Space complexity is O(n).

Code

class Solution:
    def sumSubseqWidths(self, A):
        n, M = len(A), 10**9 + 7
        coeff = [1]
        for i in range(n-1): coeff += [coeff[-1]*2%M]
        coeff = [i-j for i,j in zip(coeff, coeff[::-1])]
        return sum(x*y for x,y in zip(coeff, sorted(A))) % M