Find the Sum of Subsequence Powers

Hard
1651.

Find the Sum of Subsequence Powers

Find the Sum of Subsequence Powers is a hard coding problem on arrays, dynamic programming and sorting, asked in Google interviews.

You are given an integer array nums of length n and a positive integer k.

The power of a subsequence is the minimum absolute difference between any two of its elements.

Return the sum of the powers of all subsequences of nums that have length exactly k. Since the answer may be large, return it modulo 10^9 + 7.

Example 1

Input
nums = [1,2,3,4], k = 3
Output
4
Explanation
[1,2,3], [1,3,4], [1,2,4] and [2,3,4] each have power 1.

Example 2

Input
nums = [2,2], k = 2
Output
0
Explanation
The only subsequence has two equal elements, so its power is 0.

Example 3

Input
nums = [4,3,-1], k = 2
Output
10
Explanation
[4,3] has power 1, [4,-1] has 5 and [3,-1] has 4: 10 in total.

Constraints

  • 2 <= n == nums.length <= 50
  • -10^8 <= nums[i] <= 10^8
  • 2 <= k <= n
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {number[]} nums
 * @param {number} k
 * @return {number}
 */
var sumOfPowers = function(nums, k) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

Find the Sum of Subsequence Powers — Problem & Solution

Find the Sum of Subsequence Powers solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A hard problem.

Find the Sum of Subsequence Powers is a hard coding problem on arrays, dynamic programming and sorting, asked in Google interviews.

  • Difficulty: Hard
  • Topics: Arrays, Dynamic Programming, Sorting
  • Asked at: Google
  • Time limit: 2 s
  • Memory limit: 256 MB
  • Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby

Problem statement

You are given an integer array nums of length n and a positive integer k.

The power of a subsequence is the minimum absolute difference between any two of its elements.

Return the sum of the powers of all subsequences of nums that have length exactly k. Since the answer may be large, return it modulo 10^9 + 7.

Example 1

Input: nums = [1,2,3,4], k = 3
Output: 4
Explanation: [1,2,3], [1,3,4], [1,2,4] and [2,3,4] each have power 1.

Example 2

Input: nums = [2,2], k = 2
Output: 0
Explanation: The only subsequence has two equal elements, so its power is 0.

Example 3

Input: nums = [4,3,-1], k = 2
Output: 10
Explanation: [4,3] has power 1, [4,-1] has 5 and [3,-1] has 4: 10 in total.

Constraints

  • 2 <= n == nums.length <= 50
  • -10^8 <= nums[i] <= 10^8
  • 2 <= k <= n

Hints for Find the Sum of Subsequence Powers

  1. Hint 1

    Sort the array: a subsequence's minimum absolute difference is then the minimum gap between neighbours in it.

  2. Hint 2

    Counting subsequences whose power is exactly d is hard; counting those whose power is at least d is easy — every adjacent gap must be at least d.

  3. Hint 3

    The power is always one of the O(n^2) pairwise differences. With C(d) = number of length-k subsequences with all gaps ≥ d, sort the distinct differences d_1 < d_2 < …; exactly C(d_t) − C(d_{t+1}) subsequences have power d_t. Compute each C(d) with a prefix-sum DP in O(n · k).

How to solve Find the Sum of Subsequence Powers

After sorting, the power of a subsequence is its smallest gap between neighbours, and it is always one of the pairwise differences. Counting subsequences with every gap at least d is a simple DP; differences of those counts at consecutive candidate values give the exact count for each power.

Approach

  1. Sort nums into a. Collect the distinct pairwise differences D_1 < D_2 < … < D_m.
  2. For a threshold d, let f[j][i] be the number of length-j subsequences ending at index i with every gap ≥ d: f[1][i] = 1, and f[j][i] = sum of f[j-1][p] over p < i with a[i] − a[p] ≥ d. Those p form a prefix of the indices, so a pointer plus prefix sums gives each layer in O(n).
  3. C(d) = Σ_i f[k][i]. Compute C(D_t) for every t, with C(D_{m+1}) = 0.
  4. Return Σ_t D_t · (C(D_t) − C(D_{t+1})) modulo 10^9 + 7.

Why it works

A subsequence has power exactly D_t when its gaps are all at least D_t but not all at least the next candidate D_{t+1}; since its power is one of the candidates, nothing lies strictly between. So C(D_t) − C(D_{t+1}) counts it exactly once, and weighting by D_t sums the powers.

Complexity

  • Time — O(n^3 · k) — O(n^2) thresholds, O(n · k) each
  • Space — O(n^2)

Pitfalls

  • Equal elements give a difference of 0, which is a valid power.
  • D_t (up to 2 · 10^8) times a count modulo 10^9 + 7 overflows 32 bits — and 2^53 in JavaScript, so split the multiplication there.
  • Keep the difference of counts non-negative under the modulus.

Reference solution

Python

from typing import List

def sumOfPowers(nums: List[int], k: int) -> int:
    MOD = 10**9 + 7
    a = sorted(nums)
    n = len(a)
    diffs = sorted(set(a[j] - a[i] for i in range(n) for j in range(i + 1, n)))

    def count(d):
        # length-k subsequences whose adjacent gaps are all >= d
        dp = [1] * n
        for _ in range(k - 1):
            pre = [0] * (n + 1)
            for i in range(n):
                pre[i + 1] = (pre[i] + dp[i]) % MOD
            nd = [0] * n
            p = 0
            for i in range(n):
                while p < i and a[i] - a[p] >= d:
                    p += 1
                nd[i] = pre[p]
            dp = nd
        return sum(dp) % MOD

    counts = [count(d) for d in diffs] + [0]
    ans = 0
    for t, d in enumerate(diffs):
        ans = (ans + d * (counts[t] - counts[t + 1])) % MOD
    return ans

Java

static final long MOD = 1000000007L;

// length-k subsequences of sorted a whose adjacent gaps are all >= d
static long countGapsAtLeast(int[] a, int k, long d) {
    int n = a.length;
    long[] dp = new long[n];
    Arrays.fill(dp, 1);
    for (int len = 1; len < k; len++) {
        long[] pre = new long[n + 1];
        for (int i = 0; i < n; i++) pre[i + 1] = (pre[i] + dp[i]) % MOD;
        long[] nd = new long[n];
        int p = 0;
        for (int i = 0; i < n; i++) {
            while (p < i && (long) a[i] - a[p] >= d) p++;
            nd[i] = pre[p];
        }
        dp = nd;
    }
    long s = 0;
    for (long v : dp) s = (s + v) % MOD;
    return s;
}

public static int sumOfPowers(int[] nums, int k) {
    int[] a = nums.clone();
    Arrays.sort(a);
    int n = a.length;
    TreeSet<Long> set = new TreeSet<>();
    for (int i = 0; i < n; i++) for (int j = i + 1; j < n; j++) set.add((long) a[j] - a[i]);
    long[] diffs = new long[set.size()];
    int m = 0;
    for (long d : set) diffs[m++] = d;
    long[] counts = new long[m + 1];
    for (int t = 0; t < m; t++) counts[t] = countGapsAtLeast(a, k, diffs[t]);
    long ans = 0;
    for (int t = 0; t < m; t++) {
        long exact = (counts[t] - counts[t + 1] + MOD) % MOD;
        ans = (ans + diffs[t] % MOD * exact) % MOD;
    }
    return (int) ans;
}

C++

const long long MOD = 1000000007LL;

// length-k subsequences of sorted a whose adjacent gaps are all >= d
long long countGapsAtLeast(const vector<long long>& a, int k, long long d) {
    int n = a.size();
    vector<long long> dp(n, 1);
    for (int len = 1; len < k; len++) {
        vector<long long> pre(n + 1, 0), nd(n, 0);
        for (int i = 0; i < n; i++) pre[i + 1] = (pre[i] + dp[i]) % MOD;
        int p = 0;
        for (int i = 0; i < n; i++) {
            while (p < i && a[i] - a[p] >= d) p++;
            nd[i] = pre[p];
        }
        dp = nd;
    }
    long long s = 0;
    for (long long v : dp) s = (s + v) % MOD;
    return s;
}

int sumOfPowers(vector<int>& nums, int k) {
    vector<long long> a(nums.begin(), nums.end());
    sort(a.begin(), a.end());
    int n = a.size();
    vector<long long> diffs;
    for (int i = 0; i < n; i++) for (int j = i + 1; j < n; j++) diffs.push_back(a[j] - a[i]);
    sort(diffs.begin(), diffs.end());
    diffs.erase(unique(diffs.begin(), diffs.end()), diffs.end());
    int m = diffs.size();
    vector<long long> counts(m + 1, 0);
    for (int t = 0; t < m; t++) counts[t] = countGapsAtLeast(a, k, diffs[t]);
    long long ans = 0;
    for (int t = 0; t < m; t++) {
        long long exact = (counts[t] - counts[t + 1] + MOD) % MOD;
        ans = (ans + diffs[t] % MOD * exact) % MOD;
    }
    return (int) ans;
}

JavaScript

var sumOfPowers = function(nums, k) {
    var MOD = 1000000007;
    var mulmod = function(a, b) {
        return ((a * (b >>> 16)) % MOD * 65536 + a * (b & 65535)) % MOD;
    };
    var a = nums.slice().sort(function(p, q) { return p - q; });
    var n = a.length;
    var all = [];
    for (var i = 0; i < n; i++) for (var j = i + 1; j < n; j++) all.push(a[j] - a[i]);
    all.sort(function(p, q) { return p - q; });
    var diffs = [];
    for (var i = 0; i < all.length; i++) if (i === 0 || all[i] !== all[i - 1]) diffs.push(all[i]);
    var count = function(d) {
        // length-k subsequences whose adjacent gaps are all >= d
        var dp = new Array(n).fill(1);
        for (var len = 1; len < k; len++) {
            var pre = new Array(n + 1).fill(0);
            for (var i = 0; i < n; i++) pre[i + 1] = (pre[i] + dp[i]) % MOD;
            var nd = new Array(n).fill(0), p = 0;
            for (var i = 0; i < n; i++) {
                while (p < i && a[i] - a[p] >= d) p++;
                nd[i] = pre[p];
            }
            dp = nd;
        }
        var s = 0;
        for (var i = 0; i < n; i++) s = (s + dp[i]) % MOD;
        return s;
    };
    var counts = [];
    for (var t = 0; t < diffs.length; t++) counts.push(count(diffs[t]));
    counts.push(0);
    var ans = 0;
    for (var t = 0; t < diffs.length; t++) {
        var exact = (counts[t] - counts[t + 1] + MOD) % MOD;
        ans = (ans + mulmod(diffs[t], exact)) % MOD;
    }
    return ans;
};

Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 1199 arrays problems · the whole catalogue

Learn the technique: Arrays · Dynamic Programming