Problem

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 thewidths of all the non-empty subsequences of _nums. Since the answer may be very large, return it modulo 10^9 + 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].

Examples

Example 1

1
2
3
4
5

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

1
2

Input: nums = [2]
Output: 0

Constraints

  • 1 <= nums.length <= 10^5
  • 1 <= nums[i] <= 10^5

Solution

Approach

For each number, count how many subsequences it is the maximum and how many it is the minimum. The difference gives its total contribution to the sum of widths. We sort the array and use powers of 2 to count the number of subsequences for each position.

Let nums be sorted. For each nums[i], it is the maximum in 2^i subsequences and the minimum in 2^{n-1-i} subsequences. The answer is the sum over all i of nums[i] * (2^i - 2^{n-1-i}).

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19

#include <vector>
#include <algorithm>
using namespace std;
class Solution {
public:
    int sumSubseqWidths(vector<int>& nums) {
        const int MOD = 1e9+7;
        int n = nums.size();
        sort(nums.begin(), nums.end());
        vector<long> pow2(n);
        pow2[0] = 1;
        for (int i = 1; i < n; ++i) pow2[i] = pow2[i-1] * 2 % MOD;
        long res = 0;
        for (int i = 0; i < n; ++i) {
            res = (res + nums[i] * (pow2[i] - pow2[n-1-i] + MOD) % MOD) % MOD;
        }
        return (int)res;
    }
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15

import java.util.*;
class Solution {
    public int sumSubseqWidths(int[] nums) {
        int MOD = 1_000_000_007, n = nums.length;
        Arrays.sort(nums);
        long[] pow2 = new long[n];
        pow2[0] = 1;
        for (int i = 1; i < n; ++i) pow2[i] = pow2[i-1] * 2 % MOD;
        long res = 0;
        for (int i = 0; i < n; ++i) {
            res = (res + nums[i] * (pow2[i] - pow2[n-1-i] + MOD) % MOD) % MOD;
        }
        return (int)res;
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15

class Solution {
    fun sumSubseqWidths(nums: IntArray): Int {
        val MOD = 1_000_000_007L
        val n = nums.size
        nums.sort()
        val pow2 = LongArray(n)
        pow2[0] = 1L
        for (i in 1 until n) pow2[i] = pow2[i-1] * 2 % MOD
        var res = 0L
        for (i in 0 until n) {
            res = (res + nums[i] * ((pow2[i] - pow2[n-1-i] + MOD) % MOD)) % MOD
        }
        return res.toInt()
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12

class Solution:
    def sumSubseqWidths(self, nums: list[int]) -> int:
        MOD = 10**9 + 7
        n = len(nums)
        nums.sort()
        pow2 = [1] * n
        for i in range(1, n):
            pow2[i] = pow2[i-1] * 2 % MOD
        res = 0
        for i in range(n):
            res = (res + nums[i] * (pow2[i] - pow2[n-1-i])) % MOD
        return res
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14

impl Solution {
    pub fn sum_subseq_widths(mut nums: Vec<i32>) -> i32 {
        const MOD: i64 = 1_000_000_007;
        let n = nums.len();
        nums.sort();
        let mut pow2 = vec![1i64; n];
        for i in 1..n { pow2[i] = pow2[i-1] * 2 % MOD; }
        let mut res = 0i64;
        for i in 0..n {
            res = (res + nums[i] as i64 * (pow2[i] - pow2[n-1-i] + MOD) % MOD) % MOD;
        }
        res as i32
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12

function sumSubseqWidths(nums: number[]): number {
    const MOD = 1e9 + 7;
    const n = nums.length;
    nums.sort((a, b) => a - b);
    const pow2 = new Array(n).fill(1);
    for (let i = 1; i < n; ++i) pow2[i] = pow2[i-1] * 2 % MOD;
    let res = 0;
    for (let i = 0; i < n; ++i) {
        res = (res + nums[i] * ((pow2[i] - pow2[n-1-i] + MOD) % MOD)) % MOD;
    }
    return res;
}

Complexity

  • ⏰ Time complexity: O(n log n)
  • 🧺 Space complexity: O(n)