891. Sum of Subsequence Widths

891. Sum of Subsequence Widths (Hard)

The width of a sequence is the difference between the maximum and minimum elements in the sequence.

Given an array of integers nums, return the sum of the widths of all the non-empty subsequences of nums. Since the answer may be very large, return it modulo 109 + 7.

A subsequence is a sequence that can be derived from an array by deleting some or no elements without changing the order of the remaining elements. For example, [3,6,2,7] is a subsequence of the array [0,3,1,6,2,2,7].

 

Example 1:

Input: nums = [2,1,3]
Output: 6
Explanation: The 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.

Example 2:

Input: nums = [2]
Output: 0

 

Constraints:

• 1 <= nums.length <= 105
• 1 <= nums[i] <= 105

Companies:
Amazon

Related Topics:
Array, Math, Sorting

Solution 1. Sorting + Math

// OJ: https://leetcode.com/problems/sum-of-subsequence-widths/
// Author: github.com/lzl124631x
// Time: O(NlogU) where `U` is the number of unique elements in `A`.
// Space: O(U)
class Solution {
    long mod = 1e9 + 7;
    long modpow(long base, long exp) {
        long ans = 1;
        while (exp) {
            if (exp & 1) ans = ans * base % mod;
            exp >>= 1;
            base = base * base % mod;
        }
        return ans;
    }
    long minus(long a, long b) {
        return (a - b + mod) % mod;
    }
public:
    int sumSubseqWidths(vector<int>& A) {
        map<int, int> m;
        for (int n : A) m[n]++;
        long ans = 0, first = 0, second = 0;
        for (auto j = m.begin(); j != m.end(); ++j) {
            long p = modpow(2, j->second);
            ans = (ans + minus(first * j->first, second) * minus(p, 1) % mod) % mod;
            first = (first * p % mod + minus(p, 1)) % mod;
            second = (second * p % mod + j->first * minus(p, 1) % mod) % mod;
        }
        return ans;
    }
};

Solution 2. Sorting + Math

We can sort the array as it doesn't change the answer.

The number of subsequences with minimum A[i] and maximum A[j] is $2^{j-i-1}$.

The answer is:

$$ \sum\limits_{j>i}2^{j-i-1}\cdot(A_j-A_i)\\ =\sum\limits_{i=0}^{n-2}\sum\limits_{j=i+1}^{n-1}2^{j-i-1}\cdot(A_j-A_i)\\ =\sum\limits_{i=0}^{n-2}\sum\limits_{j=i+1}^{n-1}2^{j-i-1}\cdot A_j-\sum\limits_{i=0}^{n-2}\sum\limits_{j=i+1}^{n-1}2^{j-i-1}\cdot A_i\\ =\left[\left(2^0A_1+2^1A_2+\cdots+2^{n-2}A_{n-1}\right)+\left(2^0A_2+2^1A_3+\cdots+2^{n-3}A_{n-1}\right)+\cdots+(2^0A_{n-1})\right] -\left[\sum\limits_{i=0}^{n-2}\left(2^0+2^1+\cdots+2^{n-i-2}\right)A_i\right]\\ =\left[\sum\limits_{i=1}^{n-1}(2^i-1)A_i\right]-\left[\sum\limits_{i=0}^{n-2}(2^{n-i-1}-1)A_i\right]\\ =\sum\limits_{i=0}^{n-1}\left(2^i-2^{n-i-1}\right)A_i $$

// OJ: https://leetcode.com/problems/sum-of-subsequence-widths/
// Author: github.com/lzl124631x
// Time: O(NlogN)
// Space: O(N) This can be improved to `O(1)` if we calculate the powers on the fly.
// Ref: https://leetcode.com/problems/sum-of-subsequence-widths/solution/
class Solution {
public:
    int sumSubseqWidths(vector<int>& A) {
        sort(begin(A), end(A));
        long N = A.size(), ans = 0, mod = 1e9 + 7;
        vector<int> pow(N, 1);
        for (int i = 1; i < N; ++i) pow[i] = pow[i - 1] * 2 % mod;
        for (int i = 0; i < N; ++i) {
            ans = (ans + (pow[i] - pow[N - i - 1] + mod) % mod * A[i]) % mod;
        }
        return ans;
    }
};