Number of Great Partitions — Solution in Python, Java & C++
Number of Great Partitions solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A hard problem.
Number of Great Partitions is a hard coding problem on arrays and dynamic programming, asked in Amazon, Google, Microsoft and Sprinklr interviews.
- Difficulty: Hard
- Topics: Arrays, Dynamic Programming
- Asked at: Amazon, Google, Microsoft, Sprinklr
- 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
Split nums into two ordered, possibly empty groups — every element goes to exactly one group. The partition is great if both groups have a sum of at least k.
Return the number of great partitions, modulo 10⁹ + 7. Two partitions differ if any element is in a different group.
Example 1
Input: nums = [1,2,3,4], k = 4
Output: 6
Explanation: Six of the sixteen assignments leave both sides at 4 or more.
Example 2
Input: nums = [3,3,3], k = 4
Output: 0
Explanation: The total is 9, so one side is always under 4.
Example 3
Input: nums = [6,6], k = 2
Output: 2
Explanation: Each element must go to a different group.
Constraints
1 <= nums.length <= 10001 <= nums[i] <= 10^41 <= k <= 10^4
Hints for Number of Great Partitions
Hint 1
Count the bad partitions instead: those where at least one group falls short of
k.Hint 2
If the total is below
2kno partition can work, so the answer is 0.Hint 3
Otherwise the two groups can never both fall short, so the bad count is exactly twice the number of subsets summing to less than
k.
How to solve Number of Great Partitions
Complementary counting. There are 2ⁿ assignments in total. Subtract the bad ones: those with a group summing below k. When sum >= 2k the two groups cannot both fall short, so the bad partitions are counted exactly twice by a single subset-sum DP over sums below k.
Approach
- If
sum(nums) < 2k, return 0. - Run a 0/1-knapsack
dp[j]= subsets summing to exactlyj, forjfrom 0 tok-1. - Let
smallbe the total ofdp[0..k-1]. - Return
2ⁿ - 2 · smallmodulo 10⁹ + 7, normalising the subtraction.
Why it works
The sum >= 2k guard is what makes the doubling exact rather than an over-count: if both a subset and its complement could sum below k, that partition would be subtracted twice, and inclusion–exclusion would need a third term. With the guard, each bad partition is bad on exactly one side, so doubling a one-sided count is correct. Iterating the knapsack downwards in j is the usual 0/1 discipline — upwards would let one element be used repeatedly.
Complexity
- Time —
O(n · k) - Space —
O(k)
Pitfalls
- Without the
sum >= 2kcheck the doubling over-subtracts and the answer goes negative. - The modular subtraction can go below zero — add the modulus before the final reduction.
- Groups may be empty, and the empty group has sum 0, which is why the
j = 0bucket starts at 1.
Reference solution
Python
from typing import List
def countPartitions(nums: List[int], k: int) -> int:
MOD = 10**9 + 7
if sum(nums) < 2 * k:
return 0
dp = [0] * k
dp[0] = 1
for v in nums:
for j in range(k - 1, v - 1, -1):
dp[j] = (dp[j] + dp[j - v]) % MOD
small = sum(dp) % MOD
total = pow(2, len(nums), MOD)
return (total - 2 * small) % MODJava
public static int countPartitions(int[] nums, int k) {
final long MOD = 1000000007L;
int n = nums.length;
long sum = 0;
for (int v : nums) sum += v;
if (sum < 2L * k) return 0;
long[] dp = new long[k];
dp[0] = 1;
for (int v : nums) {
for (int j = k - 1; j >= v; j--) dp[j] = (dp[j] + dp[j - v]) % MOD;
}
long small = 0;
for (int j = 0; j < k; j++) small = (small + dp[j]) % MOD;
long total = 1;
for (int i = 0; i < n; i++) total = total * 2 % MOD;
long answer = ((total - 2 * small % MOD) % MOD + MOD) % MOD;
return (int) answer;
}C++
int countPartitions(vector<int>& nums, int k) {
const long long MOD = 1000000007LL;
int n = (int) nums.size();
long long sum = 0;
for (int v : nums) sum += v;
if (sum < 2LL * k) return 0;
vector<long long> dp(k, 0);
dp[0] = 1;
for (int v : nums) {
for (int j = k - 1; j >= v; j--) dp[j] = (dp[j] + dp[j - v]) % MOD;
}
long long small = 0;
for (int j = 0; j < k; j++) small = (small + dp[j]) % MOD;
long long total = 1;
for (int i = 0; i < n; i++) total = total * 2 % MOD;
long long answer = ((total - 2 * small % MOD) % MOD + MOD) % MOD;
return (int) answer;
}JavaScript
var countPartitions = function(nums, k) {
var MOD = 1000000007;
var n = nums.length, i, j;
var sum = 0;
for (i = 0; i < n; i++) sum += nums[i];
if (sum < 2 * k) return 0;
var dp = [];
for (j = 0; j < k; j++) dp.push(0);
dp[0] = 1;
for (i = 0; i < n; i++) {
for (j = k - 1; j >= nums[i]; j--) {
dp[j] = (dp[j] + dp[j - nums[i]]) % MOD;
}
}
var small = 0;
for (j = 0; j < k; j++) small = (small + dp[j]) % MOD;
var total = 1;
for (i = 0; i < n; i++) total = (total * 2) % MOD;
var answer = (total - 2 * small % MOD) % MOD;
return ((answer % MOD) + MOD) % MOD;
};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