BinarySearch 0426 Subsequence Widths

Problem statement

https://binarysearch.com/problems/Subsequence-Widths/

Solution

Equal to Leetcode 0891 Sum of Subsequence Widths.

Complexity

Time is O(n log n) and space is O(n).

Code

class Solution:
    def solve(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