leetcode891-sums-of-subsequence-widths

Posted on | In

Description

Given an array of integers A, consider all non-empty subsequences of A.

For any sequence S, let the width of S be the difference between the maximum and minimum element of S.

Return the sum of the widths of all subsequences of A.

As the answer may be very large, return the answer modulo 10^9 + 7.

Example 1:

1
2
3
4
5
6
Input: [2,1,3]
Output: 6
Explanation:
Subsequences are [1], [2], [3], [2,1], [2,3], [1,3], [2,1,3].
The corresponding widths are 0, 0, 0, 1, 1, 2, 2.
The sum of these widths is 6.

Idea

Previously, I perform dfs, but it sufferred from time limit. However, if you find the nature of the problem, it’s just a math problem:
The order in initial arrays doesn’t matter,
my first intuition is to sort the array.

For A[i]:
There are i smaller numbers,
so there are 2 ^ i sequences in which A[i] is maximum.
we should do res += A[i] * (2 ^ i)

There are n - i - 1 bigger numbers,
so there are 2 ^ (n - i - 1) sequences in which A[i] is minimum.
we should do res -= A[i] * 2 ^ (n - i - 1)

Done.

Time Complexity:
O(NlogN)

Code

dfs

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution(object):
    def sumSubseqWidths(self, A):
        """
        :type A: List[int]
        :rtype: int
        """
        self.res = []
        
        A = sorted(A)
        self.dfs([], 0, A)
        return sum(self.res)
    
    def dfs(self, pre, start, A):
        if start > len(A):
            return
        if len(pre) > 0:
            self.res.append(pre[-1] - pre[0])
        for i in range(start, len(A)):
            pre.append(A[i])
            self.dfs(pre[:], i+1, A)
            pre.pop()

math

1
2
3
4
5
6
7
8
9
10
11
class Solution {
public:
    int sumSubseqWidths(vector<int>& A) {
        sort(A.begin(), A.end());
        long c = 1, res = 0, mod = 1e9 + 7; 
        for (int i = 0; i < A.size(); i++, c = (c<<1) % mod) {
            res = (res + A[i] * c - A[A.size() - i - 1] * c) % mod;
        }
        return (res + mod) % mod;
    }
};

C++

Vector in C++ STL
Vectors are same as dynamic arrays with the ability to resize itself automatically when an element is inserted or deleted, with their storage being handled automatically by the container. Vector elements are placed in contiguous storage so that they can be accessed and traversed using iterators. In vectors, data is inserted at the end. Inserting at the end takes differential time, as sometimes there may be a need of extending the array. Removing the last element takes only constant time because no resizing happens. Inserting and erasing at the beginning or in the middle is linear in time.

Certain functions associated with the vector are:
Iterators

begin() – Returns an iterator pointing to the first element in the vector
end() – Returns an iterator pointing to the theoretical element that follows the last element in the vector
…