Count Ways to Distribute Candies - Practice Coding Problems

Count Ways to Distribute Candies - Problem

Dynamic Programming Hard

There are n unique candies (labeled 1 through n) and k bags. You are asked to distribute all the candies into the bags such that every bag has at least one candy.

There can be multiple ways to distribute the candies. Two ways are considered different if the candies in one bag in the first way are not all in the same bag in the second way. The order of the bags and the order of the candies within each bag do not matter.

For example, (1), (2,3) and (2), (1,3) are considered different because candies 2 and 3 in the bag (2,3) in the first way are not in the same bag in the second way (they are split between the bags (2) and (1,3)). However, (1), (2,3) and (3,2), (1) are considered the same because the candies in each bag are all in the same bags in both ways.

Given two integers, n and k, return the number of different ways to distribute the candies. As the answer may be too large, return it modulo 10⁹ + 7.

Input & Output

Example 1 — Basic Case

$ Input: n = 3, k = 2

› Output: 3

💡 Note: 3 ways to distribute 3 candies into 2 non-empty bags: (1),(2,3) or (2),(1,3) or (3),(1,2)

Example 2 — Equal Partitions

$ Input: n = 2, k = 1

› Output: 1

💡 Note: Only 1 way: put both candies (1,2) in the single bag

Example 3 — Each in Own Bag

$ Input: n = 4, k = 4

› Output: 1

💡 Note: Only 1 way: each candy goes in its own bag (1),(2),(3),(4)

Constraints

1 ≤ n ≤ 1000
1 ≤ k ≤ 1000
Answer modulo 10⁹ + 7

Visualization

Tap to expand

Understanding the Visualization

Input

n=3 unique candies, k=2 bags

Partition

Find all ways to split candies into 2 non-empty groups

Count

Total valid distributions = 3

Key Takeaway

🎯 Key Insight: This is computing Stirling numbers S(n,k) using dynamic programming with recurrence S(n,k) = k×S(n-1,k) + S(n-1,k-1)

Asked in

G Google 25 a Amazon 18 M Microsoft 15

This problem asks for Stirling numbers of the second kind S(n,k) - the number of ways to partition n distinct objects into k non-empty subsets. The optimal approach uses dynamic programming with the recurrence relation: S(n,k) = k×S(n-1,k) + S(n-1,k-1). Time: O(n×k), Space: O(k) with space optimization.

Common Approaches

Approach	Time	Space	Notes
✓ Space-Optimized 1D DP	O(n*k)	O(k)	Optimize space by using only current and previous row
2D Dynamic Programming	O(n*k)	O(n*k)	Build solutions incrementally using Stirling numbers of the second kind
Brute Force Recursion	O(k^n)	O(n)	Try all possible ways to assign each candy to bags recursively

Space-Optimized 1D DP — Algorithm Steps

Use two 1D arrays for current and previous row
Fill current row based on previous row
Swap arrays for next iteration

Visualization

Tap to expand

Step-by-Step Walkthrough

Initialize

Start with prev array for row i-1

Compute

Fill curr array using prev values

Swap

Swap arrays and continue to next row

Code -

solution.c — C

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

const int MOD = 1000000007;

int min(int a, int b) {
    return a < b ? a : b;
}

int solution(int n, int k) {
    if (n == 0 || k == 0 || k > n) {
        return 0;
    }
    if (k == 1 || k == n) {
        return 1;
    }
    
    // Use two 1D arrays
    long long* prev = (long long*)calloc(k + 1, sizeof(long long));
    long long* curr = (long long*)calloc(k + 1, sizeof(long long));
    
    // Base case
    prev[1] = 1;
    
    for (int i = 2; i <= n; i++) {
        memset(curr, 0, (k + 1) * sizeof(long long));
        curr[1] = 1;
        
        for (int j = 2; j <= min(i, k); j++) {
            curr[j] = (j * prev[j] + prev[j-1]) % MOD;
        }
        
        if (i <= k) {
            curr[i] = 1;
        }
        
        // Swap arrays
        long long* temp = prev;
        prev = curr;
        curr = temp;
    }
    
    int result = prev[k];
    free(prev);
    free(curr);
    return result;
}

int main() {
    int n, k;
    scanf("%d", &n);
    scanf("%d", &k);
    printf("%d\n", solution(n, k));
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n*k)

Two nested loops to compute each dp value

✓ Linear Growth

Space Complexity

O(k)

Only two arrays of size k needed

✓ Linear Space

23.5K Views

Medium Frequency

~25 min Avg. Time

890 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

Space-Optimized 1D DP — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler