Distribute Candies Among Children I - Video Solutions

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.