Number of Great Partitions

Hard
1052.

Number of Great Partitions

Number of Great Partitions is a hard coding problem on arrays and dynamic programming, asked in Amazon, Google, Microsoft and Sprinklr interviews.

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 <= 1000
  • 1 <= nums[i] <= 10^4
  • 1 <= k <= 10^4
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 countPartitions = function(nums, k) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

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.

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 <= 1000
  • 1 <= nums[i] <= 10^4
  • 1 <= k <= 10^4

Hints for Number of Great Partitions

  1. Hint 1

    Count the bad partitions instead: those where at least one group falls short of k.

  2. Hint 2

    If the total is below 2k no partition can work, so the answer is 0.

  3. 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

  1. If sum(nums) < 2k, return 0.
  2. Run a 0/1-knapsack dp[j] = subsets summing to exactly j, for j from 0 to k-1.
  3. Let small be the total of dp[0..k-1].
  4. Return 2ⁿ - 2 · small modulo 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 >= 2k check 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 = 0 bucket 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) % MOD

Java

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