LeetCode 0891. Sum of Subsequence Widths Solution in Java, C++, Python & Go | Explanation + Code

Description

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 <= 105
• 1 <= nums[i] <= 105

Solutions

Solution 1

PythonJavaC++Go

class Solution: def sumSubseqWidths(self, nums: List[int]) -> int: mod = 10**9 + 7 nums.sort() ans, p = 0, 1 for i, v in enumerate(nums): ans = (ans + (v - nums[-i - 1]) * p) % mod p = (p << 1) % mod return ans(code-box)

class Solution { private static final int MOD = (int) 1e9 + 7; public int sumSubseqWidths(int[] nums) { Arrays.sort(nums); long ans = 0, p = 1; int n = nums.length; for (int i = 0; i < n; ++i) { ans = (ans + (nums[i] - nums[n - i - 1]) * p + MOD) % MOD; p = (p << 1) % MOD; } return (int) ans; } }(code-box)

class Solution { public: const int mod = 1e9 + 7; int sumSubseqWidths(vector<int>& nums) { sort(nums.begin(), nums.end()); long ans = 0, p = 1; int n = nums.size(); for (int i = 0; i < n; ++i) { ans = (ans + (nums[i] - nums[n - i - 1]) * p + mod) % mod; p = (p << 1) % mod; } return ans; } };(code-box)

func sumSubseqWidths(nums []int) (ans int) { const mod int = 1e9 + 7 sort.Ints(nums) p, n := 1, len(nums) for i, v := range nums { ans = (ans + (v-nums[n-i-1])*p + mod) % mod p = (p << 1) % mod } return }(code-box)