Problem Description

Given n identical candies and k children, you are to determine in how many different ways you can distribute all the candies among the children such that each child gets at least one candy. The answer may be very large, so return it modulo 10^9 + 7.

• Input: Two integers, n (number of candies) and k (number of children).
• Output: The number of ways to distribute the candies so that each child gets at least one candy.
• All candies are identical, and all children are distinct.
• Each child must receive at least one candy.

This is a classic combinatorial problem sometimes referred to as the "stars and bars" problem with a minimum constraint.

Thought Process

At first glance, one might think to enumerate all possible ways to hand out candies, but with large n and k, this is computationally infeasible. The key insight is that since candies are identical and each child must get at least one, we can model the problem as placing n candies into k boxes (children), with each box getting at least one candy.

• Brute-force would involve generating all possible distributions, but this grows exponentially.
• We need a formula or efficient method to count valid distributions without explicitly listing them.
• We recall that for distributing n identical items into k bins with each bin non-empty, the number of ways is C(n-1, k-1) after giving each child one candy.

The problem shifts from generating all combinations to calculating a binomial coefficient efficiently under modulo arithmetic.

Solution Approach

We use the "stars and bars" theorem from combinatorics:

1. Since each child must get at least one candy, we first give one candy to each child. This uses up k candies, leaving n - k candies to distribute freely.
2. Now, we must distribute n - k identical candies among k children, with no restriction (children can get zero additional candies).
3. The number of ways to do this is C((n - k) + k - 1, k - 1) = C(n - 1, k - 1), where C(a, b) is the binomial coefficient "a choose b".
4. To compute C(n - 1, k - 1) efficiently for large values, we precompute factorials and their modular inverses using Fermat's Little Theorem.
5. If n < k, it is impossible to give each child at least one candy, so the answer is 0.

We use arrays to store factorials and modular inverses up to n. All arithmetic is done modulo 10^9 + 7 to prevent overflow.

Example Walkthrough

Let's walk through a sample input: n = 5 candies, k = 3 children.

• First, give each child one candy: 3 candies used, 2 candies left.
• Now, distribute 2 candies to 3 children, with no restrictions (some can get zero):
• We need to count the number of integer solutions to x1 + x2 + x3 = 2 where x1, x2, x3 ≥ 0.
• By stars and bars, the number of solutions is C(2 + 3 - 1, 3 - 1) = C(4, 2) = 6.
• Enumerating, the distributions are: (2,0,0), (0,2,0), (0,0,2), (1,1,0), (1,0,1), (0,1,1).

So the answer is 6, matching our calculation.

Time and Space Complexity

• Brute-force approach: Would require generating all possible partitions, which is exponential in n and k, i.e., O(k^n) or worse. Not feasible for large inputs.
• Optimized approach:
  • Precomputing factorials and inverses up to n takes O(n) time and space.
  • Each query (computing the binomial coefficient) is O(1) using precomputed arrays.
  • Total time: O(n), space: O(n).

This makes the optimized approach suitable for large values of n and k.

Summary

The problem of counting ways to distribute candies with minimum constraints is elegantly solved using combinatorics, specifically the stars and bars theorem. By reducing the problem to computing a single binomial coefficient and using modular arithmetic for efficiency, we avoid brute-force enumeration and achieve an optimal solution. The main insight is to transform the minimum constraint into a simpler equivalent problem and leverage mathematical tools for fast computation.

Code Implementation

MOD = 10**9 + 7

def countWays(n, k):
    if n < k:
        return 0
    # Precompute factorials and inverse factorials
    fact = [1] * (n + 1)
    inv_fact = [1] * (n + 1)
    for i in range(1, n + 1):
        fact[i] = fact[i-1] * i % MOD
    inv_fact[n] = pow(fact[n], MOD-2, MOD)
    for i in range(n-1, -1, -1):
        inv_fact[i] = inv_fact[i+1] * (i+1) % MOD
    def comb(a, b):
        if b < 0 or b > a:
            return 0
        return fact[a] * inv_fact[b] % MOD * inv_fact[a-b] % MOD
    return comb(n-1, k-1)
    

#include <vector>
using namespace std;
const int MOD = 1e9 + 7;

long long powmod(long long a, long long b, long long mod) {
    long long res = 1;
    while (b) {
        if (b & 1) res = res * a % mod;
        a = a * a % mod;
        b >>= 1;
    }
    return res;
}

int countWays(int n, int k) {
    if (n < k) return 0;
    vector<long long> fact(n+1, 1), inv_fact(n+1, 1);
    for (int i = 1; i <= n; ++i)
        fact[i] = fact[i-1] * i % MOD;
    inv_fact[n] = powmod(fact[n], MOD-2, MOD);
    for (int i = n-1; i >= 0; --i)
        inv_fact[i] = inv_fact[i+1] * (i+1) % MOD;
    auto comb = [&](int a, int b) -> long long {
        if (b < 0 || b > a) return 0LL;
        return fact[a] * inv_fact[b] % MOD * inv_fact[a-b] % MOD;
    };
    return comb(n-1, k-1);
}
    

class Solution {
    static final int MOD = 1000000007;
    public int countWays(int n, int k) {
        if (n < k) return 0;
        long[] fact = new long[n+1];
        long[] invFact = new long[n+1];
        fact[0] = 1;
        for (int i = 1; i <= n; ++i)
            fact[i] = fact[i-1] * i % MOD;
        invFact[n] = pow(fact[n], MOD-2);
        for (int i = n-1; i >= 0; --i)
            invFact[i] = invFact[i+1] * (i+1) % MOD;
        return (int)(fact[n-1] * invFact[k-1] % MOD * invFact[n-k] % MOD);
    }
    private long pow(long a, long b) {
        long res = 1;
        while (b > 0) {
            if ((b & 1) == 1) res = res * a % MOD;
            a = a * a % MOD;
            b >>= 1;
        }
        return res;
    }
}
    

const MOD = 1e9 + 7;

function modPow(a, b, mod) {
    let res = 1;
    a = a % mod;
    while (b > 0) {
        if (b % 2 === 1) res = res * a % mod;
        a = a * a % mod;
        b = Math.floor(b / 2);
    }
    return res;
}

function countWays(n, k) {
    if (n < k) return 0;
    let fact = Array(n+1).fill(1), invFact = Array(n+1).fill(1);
    for (let i = 1; i <= n; ++i)
        fact[i] = fact[i-1] * i % MOD;
    invFact[n] = modPow(fact[n], MOD-2, MOD);
    for (let i = n-1; i >= 0; --i)
        invFact[i] = invFact[i+1] * (i+1) % MOD;
    function comb(a, b) {
        if (b < 0 || b > a) return 0;
        return fact[a] * invFact[b] % MOD * invFact[a-b] % MOD;
    }
    return comb(n-1, k-1);
}