891. Sum of Subsequence Widths #

Problem #

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:


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.

Note:

1 <= A.length <= 20000
1 <= A[i] <= 20000

Problem Summary #

Given an integer array A, consider all non-empty subsequences of A. For any sequence S, let the width of S be the difference between the maximum element and the minimum element of S. Return the sum of the widths of all subsequences of A. Since the answer may be very large, return the answer modulo 10^9+7.

Solution Ideas #

After understanding the problem, we can see that the order of elements in the array does not affect the final sum of the widths of all subsequences.
```
  [2,1,3]:[1],[2],[3],[2,1],[2,3],[1,3],[2,1,3]
  [1,2,3]:[1],[2],[3],[1,2],[2,3],[1,3],[1,2,3]
```
For each A[i], A[i] contributes to the final result only when it is on the left or right boundary of a subsequence; when A[i] is in the middle of an interval, it does not affect the final result. First sort A[i]. After sorting, there are i numbers <= A[i], and n - i - 1 numbers >= A[i]. Therefore, A[i] will appear as the right boundary in 2^i subsequences, and as the left boundary in 2^(n-i-1) subsequences. Thus, A[i]’s contribution to the final result is A[i] * 2^i - A[i] * 2^(n-i-1). For example, for [1,4,5,7], A[2] = 5. Then there are 2^2 = 4 subsequences where 5 is the right boundary, namely [5],[1,5],[4,5],[1,4,5], and there are 2^(4-2-1) = 2 subsequences where 5 is the left boundary, namely [5],[5,7]. The effect of A[2] = 5 on the final result is 5 * 2^2 - 5 * 2^(4-2-1) = 10.
The problem asks for the sum of the widths of all subsequences, which is the total sum of each interval’s maximum value minus its minimum value. Thus Ans = SUM{ A[i]*2^i - A[n-i-1] * 2^(n-i-1) }, where 0 <= i < n. Note that 2^i may be very large, so we need to take mod during the calculation, rather than taking mod only after all calculations are complete. Pay attention to the associative property of modulo: (a * b) % c = (a % c) * (b % c) % c.

Code #


package leetcode

import (
	"sort"
)

func sumSubseqWidths(A []int) int {
	sort.Ints(A)
	res, mod, n, p := 0, 1000000007, len(A), 1
	for i := 0; i < n; i++ {
		res = (res + (A[i]-A[n-1-i])*p) % mod
		p = (p << 1) % mod
	}
	return res
}