Algorithm
Problem Name: 891. Sum of Subsequence Widths
Problem Link: https://leetcode.com/problems/sum-of-subsequence-widths/
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 109 + 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:
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:
Input: nums = [2] Output: 0
Constraints:
1 <= nums.length <= 1051 <= nums[i] <= 105
Code Examples
#1 Code Example with Javascript Programming
Code -
Javascript Programming
const sumSubseqWidths = function(A) {
A.sort((a, b) => a - b)
let c = 1, res = 0, mod = 10 ** 9 + 7
for (let i = 0, n = A.length; i < n; i++, c = c * 2 % mod) {
res = (res + A[i] * c - A[n - i - 1] * c) % mod;
}
return (res + mod) % mod;
};
Input
nums = [2,1,3]
Output
6
#2 Code Example with Python Programming
Code -
Python Programming
class Solution:
def sumSubseqWidths(self, A):
A.sort()
res=0
for i in range(len(A)):
res*=2
res-=A[i]
res+=A[~i]
return res % (10**9+7)
Input
nums = [2,1,3]
Output
6