Number of Great Partitions - Practice Coding Problems

Number of Great Partitions - Problem

You are given an array nums consisting of positive integers and an integer k.

Partition the array into two ordered groups such that each element is in exactly one group. A partition is called great if the sum of elements of each group is greater than or equal to k.

Return the number of distinct great partitions. Since the answer may be too large, return it modulo 10⁹ + 7.

Two partitions are considered distinct if some element nums[i] is in different groups in the two partitions.

Input & Output

Example 1 — Basic Case

$ Input: nums = [1,2,1], k = 2

› Output: 1

💡 Note: Only one great partition: Group A = {1,1} with sum 2, Group B = {2} with sum 2. Both sums ≥ k=2.

Example 2 — Multiple Partitions

$ Input: nums = [3,3,3], k = 4

› Output: 3

💡 Note: Three great partitions possible: A={3,3}, B={3} or A={3}, B={3,3} (counted as distinct based on element positions), and A={3} (first), B={3,3} (second,third).

Example 3 — Impossible Case

$ Input: nums = [1,1,1,1], k = 5

› Output: 0

💡 Note: Total sum is 4, but we need both groups to have sum ≥ 5. Impossible since 4 < 2×5.

Constraints

1 ≤ nums.length ≤ 1000
1 ≤ nums[i] ≤ 100
1 ≤ k ≤ 10⁹

Visualization

Tap to expand

Understanding the Visualization

Input Array

Given array nums and minimum sum k for each group

Partition Elements

Split elements into two groups A and B

Count Valid

Count partitions where sum(A) ≥ k and sum(B) ≥ k

Key Takeaway

🎯 Key Insight: Use DP to count valid partitions by tracking possible group sums, avoiding exponential enumeration

Asked in

G Google 15 f Facebook 12 a Amazon 8

The key insight is to use dynamic programming to count partitions efficiently rather than generating all 2^n possibilities. We build a DP table tracking how many ways we can achieve each possible sum, then count valid partitions where both groups have sum ≥ k. Best approach is 2D DP with Time: O(n×sum), Space: O(n×sum).

Common Approaches

Approach	Time	Space	Notes
✓ Dynamic Programming - Count Valid Partitions	O(n * sum)	O(n * sum)	Use DP to count partitions where both groups have sum >= k
Brute Force - Try All Partitions	O(2^n)	O(1)	Generate all possible ways to split array into two groups and count valid ones

Dynamic Programming - Count Valid Partitions — Algorithm Steps

Initialize DP table dp[i][sum] for counting partitions
For each element, decide which group to add it to
Count valid partitions where both group sums >= k

Visualization

Tap to expand

Step-by-Step Walkthrough

Initialize DP

Create table dp[i][sum] for partition counting

Fill Table

For each element, update all possible sums

Count Valid

Sum partitions where both groups >= k

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

long long modPow(long long base, long long exp, long long mod) {
    long long result = 1;
    while (exp > 0) {
        if (exp % 2 == 1) result = (result * base) % mod;
        base = (base * base) % mod;
        exp /= 2;
    }
    return result;
}

int solution(int* nums, int numsSize, int k) {
    const int MOD = 1000000007;
    int total = 0;
    for (int i = 0; i < numsSize; i++) total += nums[i];
    
    if (total < 2 * k) return 0;
    
    int dp[21][1001] = {0};
    dp[0][0] = 1;
    
    for (int i = 1; i <= numsSize; i++) {
        for (int s = 0; s <= total; s++) {
            dp[i][s] = dp[i-1][s];
            if (s >= nums[i-1]) {
                dp[i][s] = (dp[i][s] + dp[i-1][s - nums[i-1]]) % MOD;
            }
        }
    }
    
    long long count = 0;
    for (int s = k; s <= total - k; s++) {
        if (total - s >= k) {
            count = (count + dp[numsSize][s]) % MOD;
        }
    }
    
    long long inv2 = modPow(2, MOD - 2, MOD);
    return (count * inv2) % MOD;
}

int main() {
    char line[1000];
    fgets(line, sizeof(line), stdin);
    
    int nums[20];
    int numsSize = 0;
    char* token = strtok(line + 1, ",]");
    while (token != NULL) {
        nums[numsSize++] = atoi(token);
        token = strtok(NULL, ",]");
    }
    
    int k;
    scanf("%d", &k);
    
    printf("%d\n", solution(nums, numsSize, k));
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n * sum)

We iterate through n elements and all possible sums up to total sum

✓ Linear Growth

Space Complexity

O(n * sum)

DP table stores states for each element and possible sum

⚡ Linearithmic Space

12.4K Views

Medium Frequency

~35 min Avg. Time

387 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Dynamic Programming - Count Valid Partitions — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler