891. Sum of Subsequence Widths

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].

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