Leetcode-EIGHT-Mathematic

Leetcode-EIGHT-Mathematic
- SumofSubsequenceWidths
  - Description
  - Example
  - Analysis
  - Code

SumofSubsequenceWidths

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.

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

Example

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.

Analysis

题目的意思是很简单的，给定一个数组，求取数组的所有子序列的宽度和，其中子序列 $[a_1, a_2, …, a_n]$ 宽度定义为 $width = max {a_1, a_2, …, a_n } - min {a_1, a_2, …, a_n }$。

注意到数组的长度和数组项的大小，如果直接暴力枚举，那么不用说，TL 是妥妥的。我们需要认真考虑。我们来思考一下，答案由什么构成？答案是所有子序列的宽度，也就是子序列中的最大值与最小值的差。那么，我们考量数组内的某一个元素 $a_i$。对于 $a_i$，它对答案做贡献时，它是所在子序列最大值，或者子序列最小值。到了这里，我们的算法结果就比较明显了。我们考虑的问题变成统计每一个 $a_i$，它作为子序列最小值的个数 min 和子序列最大值的个数 max。答案就是
$$ ans = \sum_{i=1}^{n} (max - min) \times a_i$$

首先，我们对数组排序。对于有序数组 $[a_1, a_2, …, a_i, … a_n]$，$a_i$ 作为子序列最大值，只存在于 $a_1, a_2, …, a_{i-1}$ 这些项与 $a_i$ 构成的子序列，而作为最小值，只存在于 $a_{i+1}, a_{i+2}, …, a_n$ 这些项与 $a_i$ 构成的子序列。那么
$$min = 2^{i}$$
$$max = 2^{n - i - 1}$$

推出了这些数学式子，我们的算法只要对数组进行一次排序，一次扫描计算，就可以得出结果了。

Code

static int desyncio = []() {
    std::ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    return 0;
}();

class Solution {
public:
    int sumSubseqWidths(vector<int>& A) {
        sort(A.begin(), A.end());
        const long mod = 1e9 + 7;
        long res = 0, index = 1;
        int size = A.size();
        for (int i = 0; i < size; ++i) {
            res = (res + index * (A[i] - A[size-1-i])) % mod;
            index = (index << 1) % mod;
            res %= mod;
        }

        return res % mod;
    }
};