Editorial

Solution walkthrough

Review the explanation, then compare the reference implementation.

Video explanation

Solution

Intuition

Once the first child's amount is fixed, choosing the second child's amount determines the third child's amount. Instead of enumerating both, count the interval of second-child amounts that keeps both remaining children within their limits.

Approach

Try every first-child amount i from zero through min(n, limit). Let remaining = n - i. If this exceeds 2 * limit, the other two children cannot receive all remaining candies, so skip this choice.

The second child must receive at least max(0, remaining - limit) candies so the third does not exceed the limit. They can receive at most min(remaining, limit) candies. Add the number of integers in this inclusive interval to the answer. Every distribution has exactly one first-child amount and one second-child amount, so these counts are disjoint and exhaustive.

class Solution:
    def distributeCandies(self, n: int, limit: int) -> int:
        combinations = 0

        for i in range(min(n, limit) + 1):
            after_first = n - i
            if after_first > 2 * limit:
                continue
            second_at_least = max(0, after_first - limit)
            second_at_most = min(after_first, limit)
            combinations += second_at_most - second_at_least + 1

        return combinations

Complexity analysis

Time: O(min(n, limit) + 1). Auxiliary space: O(1).