Distribute Candies Among Children I solution and explanation
9 more videos on this problem
LeetCode#2928 Distribute Candies Among Children I - PythonCodeJulian · 1:00 · 1K views
2928. Distribute Candies Among Children I (Leetcode Easy)Programming Live with Larry · 3:12 · 666 views
2928. Distribute Candies Among Children I | Brute Force | BiWeekly 117Tech Courses · 2:58 · 595 views
2928 2929 Distribute Candies Among Children 1 and 2 | LeetCode | CombinatoricsR Sai Siddhu · 16:48 · 468 views
Leetcode 2928 Distribute Candies Among Children - 1Brain Box · 3:40 · 346 views
Leetcode 2928 Distribute Candies Among Children IAlgorithmicIQ · 10:34 · 161 views
Distribute Candies Among Children IToan Tran · 2:45 · 42 views
2928. Distribute Candies Among Children ISofia Bargues · 46:20 · 39 views
Day 61: 2928. Distribute Candies Among Children I. Sharon help me broMichael Chan · 14:11 · 8 views
Leetcode easy problem 2928. Distribute Candies Among Children I | devops python practiceADevOpsEngineer · 7:35 · 6 views
The problem
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 <= 501 <= 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.
def distribute_candies(n, limit, children, currentChild):
if children == currentChild:
return 1 if n == 0 else 0
ways = 0
for i in range(min(limit, n) + 1):
ways += distribute_candies(n - i, limit, children, currentChild + 1)
return ways
print(distribute_candies(5, 2, 3, 0))public class DistributeCandies {
public static int distributeCandies(int n, int limit, int children, int currentChild) {
if (children == currentChild) {
return n == 0 ? 1 : 0;
}
int ways = 0;
for (int i = 0; i <= limit && i <= n; i++) {
ways += distributeCandies(n - i, limit, children, currentChild + 1);
}
return ways;
}
public static void main(String[] args) {
System.out.println(distributeCandies(5, 2, 3, 0));
}
}#include <iostream>
int distribute(int n, int limit, int children, int currentChild) {
if (children == currentChild) {
return n == 0 ? 1 : 0;
}
int totalWays = 0;
for (int i = 0; i <= limit && i <= n; ++i) {
totalWays += distribute(n - i, limit, children, currentChild + 1);
}
return totalWays;
}
int main() {
int n = 5, limit = 2;
std::cout << distribute(n, limit, 3, 0) << std::endl;
return 0;
}function distributeCandies(n, limit, children, currentChild) {
if (children === currentChild) {
return n === 0 ? 1 : 0;
}
let ways = 0;
for (let i = 0; i <= limit && i <= n; i++) {
ways += distributeCandies(n - i, limit, children, currentChild + 1);
}
return ways;
}
console.log(distributeCandies(5, 2, 3, 0));#include <stdio.h>
int distribute_candies(int n, int limit, int children, int currentChild) {
if (children == currentChild) {
return n == 0 ? 1 : 0;
}
int ways = 0;
for (int i = 0; i <= limit && i <= n; i++) {
ways += distribute_candies(n - i, limit, children, currentChild + 1);
}
return ways;
}
int main() {
int n = 5, limit = 2;
printf("%d\n", distribute_candies(n, limit, 3, 0));
return 0;
}using System;
class Program {
static int DistributeCandies(int n, int limit, int children, int currentChild) {
if (children == currentChild) {
return n == 0 ? 1 : 0;
}
int ways = 0;
for (int i = 0; i <= limit && i <= n; i++) {
ways += DistributeCandies(n - i, limit, children, currentChild + 1);
}
return ways;
}
static void Main() {
Console.WriteLine(DistributeCandies(5, 2, 3, 0));
}
}The Python function uses backtracking to explore and count all valid distributions by splitting candies across children, respecting the specified limits.
Time Complexity: O(limit^3) given the three nested iterations up to 'limit'.
Space Complexity: O(1), ignoring recursion depth.
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.
def count_distributions(n, limit):
ways = 0
for i in range(min(limit, n) + 1):
for j in range(min(limit, n - i) + 1):
k = n - i - j
if k <= limit:
ways += 1
return ways
print(count_distributions(5, 2))public class CandyDistribution {
public static int countDistributions(int n, int limit) {
int ways = 0;
for (int i = 0; i <= limit && i <= n; i++) {
for (int j = 0; j <= limit && i + j <= n; j++) {
int k = n - i - j;
if (k <= limit) {
ways++;
}
}
}
return ways;
}
public static void main(String[] args) {
System.out.println(countDistributions(5, 2));
}
}#include <iostream>
int countDistributions(int n, int limit) {
int ways = 0;
for (int i = 0; i <= limit && i <= n; ++i) {
for (int j = 0; j <= limit && i + j <= n; ++j) {
int k = n - i - j;
if (k <= limit) {
++ways;
}
}
}
return ways;
}
int main() {
int n = 5, limit = 2;
std::cout << countDistributions(n, limit) << std::endl;
return 0;
}function countDistributions(n, limit) {
let ways = 0;
for (let i = 0; i <= limit && i <= n; i++) {
for (let j = 0; j <= limit && i + j <= n; j++) {
let k = n - i - j;
if (k <= limit) {
ways++;
}
}
}
return ways;
}
console.log(countDistributions(5, 2));#include <stdio.h>
int countDistributions(int n, int limit) {
int ways = 0;
for (int i = 0; i <= limit && i <= n; i++) {
for (int j = 0; j <= limit && i + j <= n; j++) {
int k = n - i - j;
if (k <= limit) {
ways++;
}
}
}
return ways;
}
int main() {
int n = 5, limit = 2;
printf("%d\n", countDistributions(n, limit));
return 0;
}using System;
class Program {
static int CountDistributions(int n, int limit) {
int ways = 0;
for (int i = 0; i <= limit && i <= n; i++) {
for (int j = 0; j <= limit && i + j <= n; j++) {
int k = n - i - j;
if (k <= limit) {
ways++;
}
}
}
return ways;
}
static void Main() {
Console.WriteLine(CountDistributions(5, 2));
}
}In Python, the function iterates over all possible combinations for the three children, ensuring each total fits within the defined limit, and counts these combinations.
Time Complexity: O(n × limit^2) due to loops.
Space Complexity: O(1) using only counters for configuration counting.
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).
function distributeCandies(n: number, limit: number): number {
const comb2 = (n: number) => (n * (n - 1)) / 2;
if (n > 3 * limit) {
return 0;
}
let ans = comb2(n + 2);
if (n > limit) {
ans -= 3 * comb2(n - limit + 1);
}
if (n - 2 >= 2 * limit) {
ans += 3 * comb2(n - 2 * limit);
}
return ans;
}func distributeCandies(n int, limit int) int {
comb2 := func(n int) int {
return n * (n - 1) / 2
}
if n > 3*limit {
return 0
}
ans := comb2(n + 2)
if n > limit {
ans -= 3 * comb2(n-limit+1)
}
if n-2 >= 2*limit {
ans += 3 * comb2(n-2*limit)
}
return ans
}Complexity comparison
| Approach | Complexity |
|---|---|
| Backtracking Approach | Time Complexity: O(limit^3) given the three nested iterations up to 'limit'. |
| Iterative Combinatorial Approach | Time Complexity: O(n × limit^2) due to loops. |
| Combinatorial Mathematics + Principle of Inclusion-Exclusion | – |
Complexity analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Backtracking Enumeration | O(n^2) | O(1) | When exploring all valid assignments explicitly or explaining brute-force reasoning in interviews |
| Iterative Combinatorial Counting | O(n) | O(1) | Best general solution when counting valid distributions efficiently |
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.