LeetCode 891: Sum of Subsequence Widths Solution

Master LeetCode problem 891 (Sum of Subsequence Widths), a hard challenge, with our optimized solutions in Java, C++, and Python. Explore detailed explanations, test your code in our interactive editor, and prepare for coding interviews.

891. Sum of Subsequence Widths

Hard

Array Math Sorting

Problem Explanation

Explanation

To solve this problem, we need to find the width of all possible subsequences of the given array and sum up these widths. The width of a subsequence is the difference between the maximum and minimum elements in that subsequence. We can achieve this by sorting the array and then calculating the contribution of each element to the sum.

Sort the array nums.
For each element num[i] in nums, calculate its contribution to the sum.
The contribution of num[i] is (2^i - 2^(n-1-i)) * num[i], where i is the index of the element in the sorted array and n is the length of the array.
Sum up the contributions for all elements and return the result modulo 10^9 + 7.

Time complexity: O(nlogn) where n is the length of the input array. Space complexity: O(1)

Solution Code

class Solution {
    public int sumSubseqWidths(int[] nums) {
        int mod = 1000000007;
        Arrays.sort(nums);
        int n = nums.length;
        long sum = 0;
        long pow2 = 1;
        
        for (int i = 0; i < n; i++) {
            sum = (sum + (pow2 - pow(2, n - 1 - i)) * nums[i]) % mod;
            pow2 = (pow2 * 2) % mod;
        }
        
        return (int)sum;
    }
    
    private long pow(int x, int n) {
        if (n == 0) return 1;
        long mod = 1000000007;
        long res = 1;
        long base = x;
        while (n > 0) {
            if (n % 2 == 1) {
                res = (res * base) % mod;
            }
            base = (base * base) % mod;
            n /= 2;
        }
        return res;
    }
}

Try It Yourself

Loading code editor...

Frequently Asked Questions

How to solve LeetCode 891 (Sum of Subsequence Widths)?

This page provides optimized solutions for LeetCode problem 891 (Sum of Subsequence Widths) in Java, C++, and Python, along with a detailed explanation and an interactive code editor to test your code.

What is the time complexity of LeetCode 891 (Sum of Subsequence Widths)?

The time complexity for LeetCode 891 (Sum of Subsequence Widths) varies by solution. Check the detailed explanation section for specific complexities in Java, C++, and Python implementations.

Can I run code for LeetCode 891 on DevExCode?

Yes, DevExCode provides an interactive code editor where you can write, test, and run your code for LeetCode 891 in Java, C++, or Python.

Back to LeetCode Solutions