Formatted question description: https://leetcode.ca/all/891.html

# 891. Sum of Subsequence Widths

## Level

Hard

## Description

Given an array of integers `A`

, consider all non-empty subsequences of `A`

.

For any sequence S, let the *width* of S be the difference between the maximum and minimum element of S.

Return the sum of the widths of all subsequences of A.

As the answer may be very large, **return the answer modulo 10^9 + 7**.

**Example 1:**

**Input:** [2,1,3]

**Output:** 6

**Explanation:**

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.

**Note:**

`1 <= A.length <= 20000`

`1 <= A[i] <= 20000`

## Solution

First sort the array `A`

, which won’t affect the result. Then the sum of subsequence widths is the sum over `2 ^ (j - i - 1) * (A[j] - A[i])`

for all pairs `(i, j)`

such that `0 <= i < j < A.length`

. The result is the sum over `(2 ^ i - 2 ^ (A.length - i - 1)) * A[i]`

for all `i`

from 0 to `A.length - 1`

.

```
class Solution {
public int sumSubseqWidths(int[] A) {
final int MODULO = 1000000007;
Arrays.sort(A);
int length = A.length;
long[] pow2 = new long[length];
pow2[0] = 1;
for (int i = 1; i < length; i++)
pow2[i] = pow2[i - 1] * 2 % MODULO;
long sum = 0;
for (int i = 0; i < length; i++)
sum = (sum + (pow2[i] - pow2[length - 1 - i]) * A[i]) % MODULO;
return (int) sum;
}
}
```