Sum of Subsequence Widths

hard math sorting combinatorics

Problem

The width of a sequence is the difference between its maximum and minimum element. Given an array of integers nums, return the sum of the widths of all non-empty subsequences of nums. Because the answer can be very large, return it modulo 10⁹ + 7.

Inputnums = [2, 1, 3]

Output6

The subsequences are [1],[2],[3],[2,1],[2,3],[1,3],[2,1,3] with widths 0,0,0,1,1,2,2 → total 6. Order inside a subsequence does not matter for the width.

nums (comma-separated)

def sum_subseq_widths(nums):
    MOD = 10**9 + 7
    nums.sort()
    n = len(nums)
    ans = 0
    pow2 = 1                      # 2^i, starts at 2^0
    for i in range(n):
        # nums[i] is the max of 2^i subsets, the min of 2^(n-1-i)
        ans = (ans + (pow2 - pow(2, n - 1 - i, MOD)) * nums[i]) % MOD
        pow2 = pow2 * 2 % MOD
    return ans % MOD

function sumSubseqWidths(nums) {
  const MOD = 1000000007n;
  nums.sort((a, b) => a - b);
  const n = nums.length;
  // precompute powers of two mod MOD
  const pow = new Array(n);
  pow[0] = 1n;
  for (let i = 1; i < n; i++) pow[i] = pow[i - 1] * 2n % MOD;
  let ans = 0n;
  for (let i = 0; i < n; i++) {
    const w = (pow[i] - pow[n - 1 - i] + MOD) % MOD;
    ans = (ans + w * BigInt(nums[i])) % MOD;
  }
  return Number((ans % MOD + MOD) % MOD);
}

class Solution {
    public int sumSubseqWidths(int[] nums) {
        long MOD = 1_000_000_007L;
        Arrays.sort(nums);
        int n = nums.length;
        long[] pow = new long[n];
        pow[0] = 1;
        for (int i = 1; i < n; i++) pow[i] = pow[i - 1] * 2 % MOD;
        long ans = 0;
        for (int i = 0; i < n; i++) {
            long w = (pow[i] - pow[n - 1 - i] + MOD) % MOD;
            ans = (ans + w * nums[i]) % MOD;
        }
        return (int) ((ans % MOD + MOD) % MOD);
    }
}

int sumSubseqWidths(vector<int>& nums) {
    const long long MOD = 1000000007LL;
    sort(nums.begin(), nums.end());
    int n = nums.size();
    vector<long long> pw(n);
    pw[0] = 1;
    for (int i = 1; i < n; i++) pw[i] = pw[i - 1] * 2 % MOD;
    long long ans = 0;
    for (int i = 0; i < n; i++) {
        long long w = (pw[i] - pw[n - 1 - i] + MOD) % MOD;
        ans = (ans + w * nums[i]) % MOD;
    }
    return (int) ((ans % MOD + MOD) % MOD);
}

Explanation

There are exponentially many subsequences, so we can never list them all. The key insight is that the width of a subsequence (max minus min) only depends on its biggest and smallest element, and after sorting we can count how often each value plays each role.

Sort the array. For a value at sorted index i, every subset of the i smaller elements (there are 2^i of them) makes this value the maximum. Likewise it is the minimum of 2^(n-1-i) subsequences (choosing any subset of the elements after it).

So each value contributes +nums[i] once for every time it is a max and -nums[i] once for every time it is a min. Its net weight is 2^i - 2^(n-1-i), and we add weight * nums[i] to the answer, all under MOD = 1e9+7.

Example: nums = [2, 1, 3] sorts to [1, 2, 3]. For 1: weight 2^0 - 2^2 = -3 → -3. For 2: 2^1 - 2^1 = 0 → 0. For 3: 2^2 - 2^0 = 3 → 9. Total -3 + 0 + 9 = 6, matching the expected output.

This turns an impossible enumeration into one tidy pass over the sorted values, which is why it runs in O(n log n).

Time: O(n log n) Space: O(n)