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^82 <= k <= n
Hints for Find the Sum of Subsequence Powers
Hint 1
Sort the array: a subsequence's minimum absolute difference is then the minimum gap between neighbours in it.
Hint 2
Counting subsequences whose power is exactly
dis hard; counting those whose power is at leastdis easy — every adjacent gap must be at leastd.Hint 3
The power is always one of the
O(n^2)pairwise differences. WithC(d)= number of length-ksubsequences with all gaps ≥d, sort the distinct differencesd_1 < d_2 < …; exactlyC(d_t) − C(d_{t+1})subsequences have powerd_t. Compute eachC(d)with a prefix-sum DP inO(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
- Sort
numsintoa. Collect the distinct pairwise differencesD_1 < D_2 < … < D_m. - For a threshold
d, letf[j][i]be the number of length-jsubsequences ending at indexiwith every gap ≥d:f[1][i] = 1, andf[j][i]= sum off[j-1][p]overp < iwitha[i] − a[p] ≥ d. Thosepform a prefix of the indices, so a pointer plus prefix sums gives each layer inO(n). C(d) = Σ_i f[k][i]. ComputeC(D_t)for everyt, withC(D_{m+1}) = 0.- Return
Σ_t D_t · (C(D_t) − C(D_{t+1}))modulo10^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 to2 · 10^8) times a count modulo10^9 + 7overflows 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 ansJava
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