Is Distribute Candies Among Children II easy or hard?

The problem is rated Medium on LeetCode. The brute force enumeration is straightforward, but recognizing the combinatorics structure or designing a scalable counting approach is what elevates the difficulty.

Distribute Candies Among Children II Python/Java solution

Typical implementations iterate over possible values for two children and compute the third value directly. Python, Java, C++, and similar languages can implement this in a few lines using nested loops and a validity check for the remaining candies.

How to solve Distribute Candies Among Children II in O(n)?

An even faster solution comes from combinatorics. First count all non‑negative solutions to a + b + c = n using combinations, then subtract cases where any child exceeds the limit using inclusion–exclusion. This converts the counting problem into a few constant‑time arithmetic operations, resulting in O(1) time.

What is the best approach for Distribute Candies Among Children II?

The most practical implementation approach is enumeration with constraints or dynamic programming counting. The brute force method fixes two variables and derives the third, giving O(limit^2) time and O(1) space. For more scalable variants, a DP counting approach with O(n × limit) time works well. Many advanced solutions also derive an O(1) combinatorics formula using inclusion–exclusion.

Is Distribute Candies Among Children II asked at Google/Amazon/Meta?

Problems involving constrained distributions and counting combinations appear frequently in interviews at companies like Google, Amazon, and Meta. Variants often test combinatorics reasoning, inclusion–exclusion, or dynamic programming for counting valid states.

What data structure is used in Distribute Candies Among Children II?

The brute force solution uses simple iteration with no additional data structures. The dynamic programming approach uses a one‑dimensional array where dp[i] stores the number of ways to form i candies after processing some children.

What is the time complexity of Distribute Candies Among Children II?

The straightforward nested loop enumeration runs in O(limit^2) time because two children are iterated explicitly while the third value is computed. A dynamic programming solution runs in O(n × limit) time by building ways to reach each candy sum. Space complexity is O(1) for brute force and O(n) for DP.

Description Hints 4 Solution Video 44:16

2929. Distribute Candies Among Children II

Medium55.7% acceptance5 companies

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 <= 10⁶
1 <= limit <= 10⁶

Asked at 5 companies

PhonePe Rubrik Amazon

Google Meta

Topics

Hints open one at a time

Hint 1

We can enumerate the number of candies of one particular child, let it be i which means 0 <= i <= min(limit, n).

Hint 2

Suppose the 2nd child gets j candies. Then 0 <= j <= limit and i + j <= n.

Hint 3

The 3rd child will hence get n - i - j candies and we should have 0 <= n - i - j <= limit.

Hint 4

After some transformations, for each i, we have max(0, n - i - limit) <= j <= min(limit, n - i), each j corresponding to a solution. So the number of solutions for some i is max(min(limit, n - i) - max(0, n - i - limit) + 1, 0). Sum the expression for every i in [0, min(n, limit)].

44:16

Still stuck?Read 3 approaches, or watch a walkthrough.

Open solution