Problem Explanation

You are given an array of integers. The task is to consider all the non-empty subsequences in the array. From each subsequence, subtract the smallest value in each subsequence from the largest value to give the 'width'. Sum up all these widths and return the sum.

The array will be of length from 1 - 20000, where each element in the array ranges from 1 - 20000.

Approach

The quickest way to do this is to sort the array in ascending order. After the array is sorted, the smallest number and largest numbers will be at the start and end of the array respectively.

Think about the elements as binary numbers. Each number will appear (2^i) times as the max element and (2^(n-i-1)) times as the min element, where n is the number of elements in the array and i is the index position of a number in the array.

For each number in the sorted array, add ((nums[i] - nums[n - i - 1]) * exp) to the answer, where exp is (2^i)%1000000007.

This is a mathematical trick that takes use of how the numbers are arranged in the list after sorting it in descending order.

The time complexity of this algorithm is O(n log n) because of sorting, and the space complexity is O(1).

Example

Let's walk through an example with array [2,1,3]. The array is already sorted.

Index 0: (nums[0] - nums[n - 0 - 1]) * exp = (1 - 3) * 1 = -2 Index 1: (nums[1] - nums[n - 1 - 1]) * exp = (2 - 2) * 2 = 0 Index 2: (nums[2] - nums[n - 2 - 1]) * exp = (3 - 1) * 4 = 8

So the sum of subsequence widths is -2 + 0 + 8 = 6.

Python Solution

1
2python
3class Solution:
4    def sumSubseqWidths(self, A):
5        A.sort()
6        mod = 10**9 + 7
7        pow2 = [1]
8        for i in range(1, len(A)):
9            pow2.append(pow2[-1] * 2 % mod)
10        res = 0
11        for i, a in enumerate(A):
12            res = (res + (pow2[i] - pow2[len(A) - i - 1]) * a) % mod
13        return res

Java Solution

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

C++ Solution

1
2c++
3class Solution {
4public:
5    int sumSubseqWidths(vector<int>& A) {
6        sort(A.begin(), A.end());
7        long c = 1, res = 0, mod = 1e9+7, n = A.size();
8        for (int i = 0; i < n; ++i, c = (c << 1) % mod)
9            res = (res + A[i] * c - A[n - 1 - i] * c) % mod;
10        return (res + mod) % mod;
11    }
12};

C# Solution

1
2csharp
3public class Solution {
4    const int mod = 1000_000_007;
5    
6    public int SumSubseqWidths(int[] A) {
7        Array.Sort(A);
8        long c = 1, res = 0, n = A.Length;
9        for (int i = 0; i < n; i++, c = (c << 1) % mod)
10            res = (res + A[i] * c - A[n - 1 - i] * c) % mod;
11        return (int)((res + mod) % mod);
12    }
13}

Javascript Solution

1
2javascript
3var sumSubseqWidths = function(A) {
4    A.sort((a, b) => a - b);
5    const mod = 10**9 + 7;
6    let pow2 = [1];
7    for (let i = 1; i < A.length; ++i){
8        pow2.push((pow2[pow2.length - 1] << 1) % mod)
9    }
10    let res = 0
11    for (let i = 0; i < A.length; ++i) {
12        res = (res + (pow2[i] - pow2[A.length - i - 1]) * A[i]) % mod
13    }
14    return res
15};

Ruby Solution

1
2ruby
3def sum_subseq_widths(a)
4    a.sort!
5    pow2 = [1]
6    mod = 10**9 + 7
7    (1...a.length).to_a.each do |i|
8        pow2.push((pow2[-1] << 1) % mod)
9    end
10    res = 0
11    a.each_with_index do |val, idx|
12        res = ((res + (pow2[idx] - pow2[a.length - idx - 1]) * val) % mod + mod) % mod
13    end
14    return res
15end

In the ruby solution, we start by sorting the input array. We then generate an array of powers of 2, modded to prevent overflow. After that, we iterate over each element in the sorted array and calculate the sum of subsequence widths using the provided formula. The return value is the final sum of subsequence widths, which gives us our answer.

PHP Solution

1
2php
3function sumSubseqWidths($A) {
4    sort($A);
5    $pow2 = array(1);
6    $mod = pow(10, 9) + 7;
7    for ($i = 1; $i < sizeof($A); $i++) {
8        array_push($pow2, ($pow2[sizeof($pow2) - 1] << 1) % $mod);
9    }
10    $res = 0;
11    for ($i = 0; $i < sizeof($A); $i++) {
12        $res = ($res + ($pow2[$i] - $pow2[sizeof($A) - $i - 1]) * $A[$i]) % $mod;
13    }
14    return $res;
15}

In PHP, the logic remains same as that of Python, Java, JavaScript, C++, C#, and Ruby solutions. We sort the array first and calculate the powers of 2. After that we iterate over each array element, for each array element we subtract the smallest value from the largest value, the result is then multiplied by power of two and is added to the final result.

In this way, using the same logical approach, we solved the problem in various programming languages including Python, Java, C++, C#, JavaScript, Ruby, and PHP. Happy coding!