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

Find the Sum of Subsequence Powers

Number: 3316

Difficulty: Hard

Paid? No

Companies: Google, Rubrik

Problem Description

Given an integer array nums of length n and a positive integer k, consider every subsequence (i.e. combination) of nums of length k. The “power” of a subsequence is defined as the minimum absolute difference between any two elements in that subsequence. Return the sum of the powers of all such subsequences modulo 10^9+7.

Key Insights

  • Sorting the array makes it easier to reason about differences; in a sorted subsequence the minimum gap is simply the smallest difference between two consecutive elements.
  • Instead of computing the power for each subsequence separately, observe that for a subsequence S the minimum gap can be represented by:   power(S) = sum { for d >= 1 of indicator[S has all adjacent differences >= d] }.
  • This lets us swap the order of summation: the answer equals sum_{d>=1} F(d) modulo MOD, where F(d) is the number of subsequences of length k with all adjacent gaps (in sorted order) at least d.
  • Dynamic programming is used to count F(d) given a “gap threshold” d.
  • F(d) is a non‐increasing step function (as d increases, fewer subsequences satisfy the condition) so we can compute it only at a few “breakpoints” and sum over intervals where F(d) remains constant.

Space and Time Complexity

Time Complexity: O(M * n^2) where M is the number of candidate gap thresholds (at most O(n)) and n ≤ 50. Space Complexity: O(n * k) for the recursion/memoization states.

Solution

The main idea is to first sort the array. For any chosen threshold d, count the number of k-length subsequences whose consecutive elements (in sorted order) differ by at least d using a recursive DP with memoization. Then, rather than summing F(d) for every integer d from 1 up to the maximum possible gap (which can be very large), we note that F(d) only changes when d reaches one of a small set of candidate values. In particular, the candidate thresholds include 1 and every distinct positive difference between consecutive elements in the sorted array. We then build intervals [L, R) over which F(d) remains constant and for each interval add count* (R-L) to the answer (all modulo 10^9+7).

The solution uses:  • Sorting  • Recursion with memoization (dynamic programming) to count valid subsequences under a gap constraint.  • A sweep over candidate gap intervals.

Code Solutions

MOD = 10**9 + 7

# Helper function using DP to count subsequences with adjacent gaps >= gap.
def count_subsequences(a, k, gap):
    n = len(a)
    memo = {}
    def dp(prev, i, r):
        # r: how many more elements to select
        if r == 0:
            return 1
        if i >= n:
            return 0
        key = (prev, i, r)
        if key in memo:
            return memo[key]
        # Option 1: Skip element at i.
        ways = dp(prev, i + 1, r)
        # Option 2: Take element at i if allowed.
        if prev == -1 or a[i] - a[prev] >= gap:
            ways += dp(i, i + 1, r - 1)
        memo[key] = ways
        return ways
    return dp(-1, 0, k)

def sumSubsequencePowers(nums, k):
    a = sorted(nums)
    n = len(a)
    # Identify candidate gap thresholds: always include 1 and the positive differences between consecutive elements.
    candidates = set([1])
    for i in range(n - 1):
        diff = a[i+1] - a[i]
        if diff > 0:
            candidates.add(diff)
    max_gap = a[-1] - a[0]
    cand_list = sorted(candidates)

    # Build intervals [L, R) where F(d) remains constant.
    intervals = []
    prev_break = 1
    for d in cand_list:
        if d > prev_break:
            intervals.append((prev_break, d))
        intervals.append((d, d+1))
        prev_break = d+1
    if prev_break <= max_gap:
        intervals.append((prev_break, max_gap+1))
    
    total = 0
    # For each interval compute F(d) at d = L (since it's constant for d in [L, R))
    for L, R in intervals:
        memo_dp = {}
        def dp(prev, i, r):
            if r == 0:
                return 1
            if i >= n:
                return 0
            key = (prev, i, r)
            if key in memo_dp:
                return memo_dp[key]
            ways = dp(prev, i + 1, r)
            if prev == -1 or a[i] - a[prev] >= L:
                ways += dp(i, i + 1, r - 1)
            memo_dp[key] = ways
            return ways
        count = dp(-1, 0, k)
        total = (total + count * (R - L)) % MOD
    return total

# Example usages:
print(sumSubsequencePowers([1,2,3,4], 3))  # Expected output: 4
print(sumSubsequencePowers([2,2], 2))      # Expected output: 0
print(sumSubsequencePowers([4,3,-1], 2))   # Expected output: 10
← Back to All Questions