# Sum Of Subsequence Widths Problem

## Description

LeetCode Problem 891.

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

Example 1:

``````1
2
3
4
5
Input: nums = [2,1,3]
Output: 6
Explanation: The subsequences are , , , [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 = 
Output: 0
``````

Constraints:

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

## Sample C++ Code

``````1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
public:
int sumSubseqWidths(vector<int>& arr) {
sort(arr.begin(), arr.end());
long power = 1, res = 0, mod = 1e9 + 7, n = arr.size();

// number of times this item will be maximum
for (int i = 0; i < n; i++) {
res = (res + arr[i] * power) % mod;
power = (power * 2) % mod;
}

// subtracting minimums
// number of times this item will be minimum
power = 1;
for (int i = n-1; i >= 0; i--) {
res = (res - arr[i] * power + mod) % mod;
power = (power * 2) % mod;
}
return (res + mod) % mod;
}
};
``````