Distribute candies among children ii

Math Combinatorics Enumeration

55.7% acceptance

Feb 25, 2026

564

176

You are given two positive integers n and limit. Return the total number of ways to distribute n candies among 3 children such that no child gets more than limit candies.

Solution

Rust

Time O(1)

Space O(1)

LeetCode

solution.rs

impl Solution {
  pub fn distribute_candies(n: i32, limit: i32) -> i64 {
    // Inclusion-exclusion: count x1+x2+x3=n with 0<=xi<=limit
    // Let f(m) = C(m+2,2) = m*(m+1)/2 for m>=0, else 0 (stars and bars count for xi>=0, sum=m among 3)
    let f = |rem: i64| -> i64 {
      if rem < 0 { 0 } else { (rem + 1) * (rem + 2) / 2 }
    };
    let l1 = limit as i64 + 1;
    f(n as i64) - 3 * f(n as i64 - l1) + 3 * f(n as i64 - 2 * l1) - f(n as i64 - 3 * l1)
  }
}