We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Count Ways to Distribute Candies

Number: 1828

Difficulty: Hard

Paid? Yes

Companies: Google

Problem Description

Given n unique candies and k bags, count the number of ways to distribute all the candies into the bags so that every bag contains at least one candy. Two distributions are considered different if there exists at least one bag whose set of candies in one distribution does not exactly match any bag's set in the other distribution. Return the answer modulo 10^9 + 7.

Key Insights

  • The problem is equivalent to partitioning n distinct items into k non-empty, unlabeled subsets.
  • This counting is given by the Stirling numbers of the second kind.
  • The recurrence relation is: dp[n][k] = dp[n-1][k-1] + k * dp[n-1][k].
  • Base condition: dp[0][0] = 1, with all other invalid partitions being 0.
  • Use dynamic programming with modulo arithmetic to efficiently compute the result.

Space and Time Complexity

Time Complexity: O(n * k)
Space Complexity: O(n * k)

Solution

We employ a dynamic programming approach using a 2D table dp where dp[i][j] represents the number of ways to partition i candies into j bags. For each candy, we either start a new bag (using dp[i-1][j-1]) or place it in one of the j existing bags (contributing j * dp[i-1][j]). We take all operations modulo 10^9 + 7 to manage large numbers. This method ensures that every bag has at least one candy and computes the answer efficiently.

Code Solutions

# Python solution using dynamic programming

MOD = 10**9 + 7

def countWaysToDistributeCandies(n: int, k: int) -> int:
    # dp[i][j] represents the number of ways to distribute i candies into j bags
    dp = [[0] * (k + 1) for _ in range(n + 1)]
    dp[0][0] = 1  # Base case: 0 candies into 0 bags
    
    for i in range(1, n + 1):
        # j cannot be more than i (since each bag must have at least one candy)
        for j in range(1, min(i, k) + 1):
            # Option 1: Use current candy to begin a new bag: dp[i-1][j-1]
            # Option 2: Add current candy to one of the existing j bags: j * dp[i-1][j]
            dp[i][j] = (dp[i-1][j-1] + j * dp[i-1][j]) % MOD
            
    return dp[n][k]

# Example usage:
n = 4
k = 2
print(countWaysToDistributeCandies(n, k))  # Expected output: 7
← Back to All Questions