Skip to main content
Talentd

Distribute Candies Among Children I - Solution & Explanation

EasyMathCombinatoricsEnumeration19 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 <= 50
  • 1 <= limit <= 50

Approach Overview

Problem Overview: You have n identical candies and 3 children. Each child can receive at most limit candies. Count how many valid distributions exist where the total number of candies given equals n.

Approach 1: Backtracking Enumeration (Time: O(n^2), Space: O(1) auxiliary)

This method explicitly enumerates possible distributions. Assign candies to the first child from 0 to limit, then assign candies to the second child within the remaining budget, and compute what the third child must receive. If the third child's value is within [0, limit], the distribution is valid. Conceptually this is a backtracking or exhaustive enumeration approach where you try combinations and prune invalid states when the remaining candies become negative or exceed the limit.

The key idea is simple iteration over feasible assignments while ensuring the total sum equals n. This approach is easy to implement and mirrors the thinking process of manually distributing candies. It falls under enumeration and basic math reasoning.

Approach 2: Iterative Combinatorial Counting (Time: O(n), Space: O(1))

Instead of exploring every triple explicitly, iterate the number of candies given to the first child. Suppose the first child receives x. The remaining candies are n - x, which must be split between the other two children. For the second child, valid values must satisfy both the remaining sum and the limit constraint. That creates a bounded range max(0, n - x - limit) to min(limit, n - x). The number of valid assignments for the second child equals the size of this interval, and the third child's candies are automatically determined.

This converts the problem into counting valid integer solutions rather than generating them. The insight comes from combinatorics: once the first child is fixed, the remaining distribution becomes a constrained two-variable equation. Iterating x from 0 to limit and summing the valid counts gives the final answer efficiently.

Recommended for interviews: The combinatorial counting approach is preferred. It demonstrates that you can convert a brute-force enumeration into a mathematical counting problem and reduce complexity to O(n) with constant space. Starting with the brute-force reasoning is still useful because it shows understanding of the constraints before optimizing.

Approach 1: Backtracking Approach

This approach involves exploring all possible distributions of candies among the children using backtracking. We try distributing candies to each child recursively and backtrack when an invalid distribution is reached. This ensures that we count all valid ways to distribute candies.

The C solution recursively distributes candies among the children while respecting the condition that no child receives more than the given limit. Each recursive call attempts to distribute a certain number of candies to the current child and then proceeds to the next.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

Time Complexity: O(limit^3) since there are three children and each child can take up to 'limit' candies.
Space Complexity: O(1) if we ignore recursion stack space.

Try this approach in the editor →

Approach 2: Iterative Combinatorial Approach

This approach uses a nested loop to iterate over all possible combinations of candy distributions to the three children. By explicitly looping through possibilities in a structured way, we count valid combinations that respect each child's candy limit.

The C implementation uses a triple nested loop to count all valid combinations. Each loop assigns candies to one child, checking that the remaining amount for the third child does not exceed the limit.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

Time Complexity: O(n × limit^2) as it iterates over children with nested loops.
Space Complexity: O(1) since we simply count configurations.

Try this approach in the editor →

Approach 3: Combinatorial Mathematics + Principle of Inclusion-Exclusion

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 →

Complexity Comparison

ApproachComplexity
Backtracking Approach

Time Complexity: O(limit^3) since there are three children and each child can take up to 'limit' candies.
Space Complexity: O(1) if we ignore recursion stack space.

Iterative Combinatorial Approach

Time Complexity: O(n × limit^2) as it iterates over children with nested loops.
Space Complexity: O(1) since we simply count configurations.

Combinatorial Mathematics + Principle of Inclusion-Exclusion—

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Backtracking EnumerationO(n^2)O(1)When exploring all valid assignments explicitly or explaining brute-force reasoning in interviews
Iterative Combinatorial CountingO(n)O(1)Best general solution when counting valid distributions efficiently

Video Solution

LeetCode#2928 Distribute Candies Among Children I - Python • CodeJulian • 1,262 views views

Watch 9 more video solutions →

Frequently Asked Questions

Is Distribute Candies Among Children I easy or hard?
The problem is classified as Easy on LeetCode with an acceptance rate above 70%. The main challenge is recognizing that the task is counting bounded integer solutions rather than generating every combination.
Distribute Candies Among Children I Python/Java solution
In Python or Java, implement a loop for the first child's candies and compute the valid range for the second child using min and max bounds. Add the size of the valid interval to the answer. The logic uses only integer arithmetic and runs in O(n) time with constant extra space.
How to solve Distribute Candies Among Children I in O(n)?
Iterate the number of candies given to the first child from 0 to limit. For each value x, compute the remaining candies r = n - x. The second child can take values from max(0, r - limit) to min(limit, r). The number of integers in this range gives the valid distributions for that iteration. Summing these counts yields the final answer in O(n) time.
What is the best approach for Distribute Candies Among Children I?
The best approach is an iterative combinatorial counting method. Iterate the candies given to the first child, then compute the valid range for the second child using the remaining candies and the per-child limit. The third child's value is determined automatically. This reduces the problem to O(n) time and O(1) space.
Is Distribute Candies Among Children I asked at Google/Amazon/Meta?
Problems involving constrained distributions and integer equations frequently appear in interviews at companies like Google, Amazon, and Meta. While this exact question may not always appear, the underlying pattern—counting bounded integer solutions using combinatorics—is a common interview concept.
What data structure is used in Distribute Candies Among Children I?
No complex data structures are required. The solution relies on simple arithmetic and iteration. The core idea comes from combinatorics and enumeration rather than arrays, stacks, or hash maps.
What is the time complexity of Distribute Candies Among Children I?
The optimized combinatorial solution runs in O(n) time because it iterates possible values for the first child's candies once and counts valid assignments mathematically. Space complexity is O(1). A naive enumeration approach may take O(n^2) time depending on how many combinations are checked.

Ready to solve this problem?

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

Practice on FleetCode
Previous

Count Ways to Distribute Candies