Skip to main content
Talentd

Distribute Candies Among Children III - Solution & Explanation

HardPremiumFree on FleetCodeMathCombinatorics11 min readAsked at: Amazon, Rubrik
Practice this problem

Problem Statement

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.

 

Example 1:

Input: n = 5, limit = 2
Output: 3
Explanation: There are 3 ways to distribute 5 candies such that no child gets more than 2 candies: (1, 2, 2), (2, 1, 2) and (2, 2, 1).

Example 2:

Input: n = 3, limit = 3
Output: 10
Explanation: There are 10 ways to distribute 3 candies such that no child gets more than 3 candies: (0, 0, 3), (0, 1, 2), (0, 2, 1), (0, 3, 0), (1, 0, 2), (1, 1, 1), (1, 2, 0), (2, 0, 1), (2, 1, 0) and (3, 0, 0).

 

Constraints:

  • 1 <= n <= 108
  • 1 <= limit <= 108

Approach Overview

Problem Overview: You are given n candies and three children. Each child can receive at most limit candies. The task is to count how many valid distributions exist such that the total candies distributed equals n while no child exceeds the limit.

This is a classic counting problem. Without restrictions, distributing n identical items across three variables (a + b + c = n) can be solved using the stars and bars formula. The challenge comes from the upper bound constraint (a, b, c ≤ limit). Handling that constraint efficiently leads to a combinatorics-based solution.

Approach 1: Enumerate Valid Pairs (Brute Force Iteration) (Time: O(limit^2), Space: O(1))

Iterate over the candies given to the first two children. For each pair (a, b), compute c = n - a - b. The distribution is valid if 0 ≤ a ≤ limit, 0 ≤ b ≤ limit, and 0 ≤ c ≤ limit. This brute force approach checks every feasible pair and increments a counter when the third child also satisfies the constraint. It works because the number of children is fixed at three, but the nested iteration makes it quadratic in the worst case.

This approach is straightforward and useful for validating logic during development. However, it becomes inefficient when limit is large.

Approach 2: Combinatorial Mathematics + Principle of Inclusion-Exclusion (Time: O(1), Space: O(1))

First ignore the upper bound. The number of ways to distribute n candies among three children is given by the stars and bars formula: C(n + 2, 2). This counts all non‑negative integer solutions to a + b + c = n.

Next remove distributions where at least one child exceeds the limit. If child a gets more than limit, substitute a' = a - (limit + 1). The equation becomes a' + b + c = n - (limit + 1). The number of such solutions is C(n - limit + 1, 2). Apply the same logic for each child.

However, subtracting these individually double‑counts cases where two children exceed the limit. The combinatorics technique called the principle of inclusion‑exclusion fixes this by adding back intersections of invalid sets. With only three variables, the formula remains small and can be computed with a few combination calculations.

This turns the entire counting process into constant time arithmetic. No loops are required, and the memory footprint stays constant. Problems involving bounded integer solutions often reduce to this exact pattern using mathematical counting.

Recommended for interviews: The combinatorial + inclusion‑exclusion solution is what interviewers expect. It shows that you recognize the equation a + b + c = n as a stars‑and‑bars problem and know how to enforce upper bounds mathematically. Mentioning the brute force iteration first demonstrates understanding, but deriving the O(1) combinatorial formula demonstrates stronger problem‑solving skills.

Solution

According to the problem description, we need to distribute n candies to 3 children, with each child receiving between [0, limit] candies.

This is equivalent to placing n balls into 3 boxes. Since the boxes can be empty, we can add 3 virtual balls, and then use the method of inserting partitions, i.e., there are a total of n + 3 balls, and we insert 2 partitions among the n + 3 - 1 positions, thus dividing the actual n balls into 3 groups, and allowing the boxes to be empty. Therefore, the initial number of schemes is C_{n + 2}^2.

We need to exclude the schemes where the number of balls in a box exceeds limit. Consider that there is a box where the number of balls exceeds limit, then the remaining balls (including virtual balls) have at most n + 3 - (limit + 1) = n - limit + 2, and the number of positions is n - limit + 1, so the number of schemes is C_{n - limit + 1}^2. Since there are 3 boxes, the number of such schemes is 3 times C_{n - limit + 1}^2. In this way, we will exclude too many schemes where the number of balls in two boxes exceeds limit at the same time, so we need to add the number of such schemes, i.e., 3 times C_{n - 2 times limit}^2.

The time complexity is O(1), and the space complexity is O(1).

Code

PythonJavaC++GoTypeScript

Python

Java

C++

Go

TypeScript

Try this approach in the editor →

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Enumerate Valid Pairs (Brute Force)O(limit^2)O(1)Useful for understanding the constraints or validating logic for small limits
Combinatorial Mathematics + Inclusion‑ExclusionO(1)O(1)Optimal approach for large n and limit; standard mathematical solution expected in interviews

Video Solution

2927. Distribute Candies Among Children III - Week 1/5 Leetcode June Challenge • Programming Live with Larry • 368 views views

Frequently Asked Questions

Is Distribute Candies Among Children III easy or hard?
The problem is rated Hard because recognizing the combinatorial structure is not obvious. Once you identify the stars and bars formulation and apply inclusion-exclusion to enforce the limit constraint, the implementation becomes short and efficient.
Distribute Candies Among Children III Python/Java solution
The implementation computes combinations such as C(n+2,2) and adjusts counts using inclusion-exclusion for each child exceeding the limit. The logic is identical across Python, Java, C++, Go, and TypeScript and runs in constant time with simple arithmetic operations.
How to solve Distribute Candies Among Children III in O(1)?
Treat the distribution as the equation a + b + c = n. Without constraints the number of solutions is C(n+2,2). Then apply inclusion-exclusion to remove cases where a, b, or c exceed the limit by transforming variables such as a' = a − (limit+1). Evaluating these combinations directly gives a constant-time solution.
What is the best approach for Distribute Candies Among Children III?
The optimal approach uses combinatorial mathematics with the principle of inclusion-exclusion. First count all solutions to a + b + c = n using the stars and bars formula C(n+2,2). Then subtract distributions where a child exceeds the limit and correct overlaps using inclusion-exclusion. This computes the result in O(1) time and O(1) space.
Is Distribute Candies Among Children III asked at Google/Amazon/Meta?
Combinatorics and counting problems using stars and bars or inclusion-exclusion frequently appear in interviews at companies like Google, Amazon, and Meta. While the exact problem may vary, the mathematical technique used here is a common interview pattern.
What data structure is used in Distribute Candies Among Children III?
No special data structure is required. The problem relies purely on mathematical counting using combinations and the inclusion-exclusion principle. The implementation typically uses a helper function to compute nCk values.
What is the time complexity of Distribute Candies Among Children III?
The optimal combinatorial solution runs in O(1) time because it only evaluates a small number of combination formulas. No iteration over candies or limits is required. Space complexity is also O(1) since only a few integer calculations are performed.

Ready to solve this problem?

Practice Distribute Candies Among Children III with our built-in code editor and test cases.

Practice on FleetCode
Previous

Add Two Numbers

Next

Reverse Integer