We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Sum of Subsequence Widths

Number: 927

Difficulty: Hard

Paid? No

Companies: Sapient

Problem Description

Given an array of integers, compute the sum of the widths of all non-empty subsequences. The width of a subsequence is defined as the difference between its maximum and minimum element. Since the answer can be very large, return it modulo 10^9 + 7.

Key Insights

  • Sort the array so that the relative order makes it easier to count contributions.
  • In a sorted array, each element can serve as the minimum in some subsequences and as the maximum in others.
  • The number of subsequences where the element at index i is the maximum is 2^i.
  • Similarly, the number where it is the minimum is 2^(n-1-i).
  • The contribution of a given element is its value multiplied by (2^i - 2^(n-1-i)).
  • Summing these contributions over all elements and taking mod 10^9 + 7 gives the answer.

Space and Time Complexity

Time Complexity: O(n log n) due to sorting plus O(n) for iteration, overall O(n log n)
Space Complexity: O(n) for storing precomputed powers modulo 10^9 + 7

Solution

The solution follows these steps:

  1. Sort the input array.
  2. Precompute powers of 2 modulo 10^9 + 7 for indices from 0 to n-1.
  3. For each element at index i in the sorted array, calculate its contribution:
    • When considered as the maximum, it appears in 2^i subsequences.
    • When considered as the minimum, it appears in 2^(n-1-i) subsequences.
  4. Subtract the minimum contribution from the maximum contribution and aggregate the results.
  5. Return the final answer modulo 10^9 + 7.

Data Structures:

  • Sorted array.
  • Auxiliary array for precomputed powers of 2.

Algorithmic Approach:

  • Sorting the array ensures that when iterating from left to right, elements before index i are always smaller, and those after are larger.
  • Modular arithmetic is used throughout the solution to manage large numbers and to ensure results stay within the required limits.

Code Solutions

# Python code solution for Sum of Subsequence Widths

MOD = 10**9 + 7

def sumSubseqWidths(nums):
    # Sort the numbers
    nums.sort()
    n = len(nums)
    
    # Precompute powers of 2 modulo MOD
    pow2 = [1] * n
    for i in range(1, n):
        pow2[i] = (pow2[i - 1] * 2) % MOD
    
    result = 0
    # Compute each element's contribution
    for i in range(n):
        # nums[i] as maximum in 2^i subsequences
        max_contrib = nums[i] * pow2[i] % MOD
        # nums[i] as minimum in 2^(n-1-i) subsequences
        min_contrib = nums[i] * pow2[n - 1 - i] % MOD
        result = (result + max_contrib - min_contrib) % MOD
    
    return result

# Example usage:
print(sumSubseqWidths([2,1,3]))  # Expected output: 6
← Back to All Questions