[Leetcode] 2929. Distribute Candies Among Children II

https://leetcode.com/problems/distribute-candies-among-children-ii/description/?envType=daily-question&envId=2025-06-01

initial

very easy to count all valid cases by dfs but initial approach was wrong.

I set the end recur condition as if index==2 and rest==0. But actually this recurs forever cuz if rest isnt 0, then even when we reach final index, we recur forever.

Also idnex shouldnt be 2 it should be 3. Cuz if we dfs from (0,n) so idx=0. When idx=1, rest is subtracted once. When idx=2, rest is subtracted twice. We need to subtract three times so the end condition should be if idx==3, not 2.

sol TLE

import sys
sys.setrecursionlimit(100000)
class Solution:
    def distributeCandies(self, n: int, limit: int) -> int:
        ans=0
        def dfs(idx,rest):
            nonlocal ans
            if idx==3:
                if rest==0:
                    ans+=1
                return
            for i in range(limit+1):
                dfs(idx+1,rest-i)
        dfs(0,n)
        return ans

math sol

We have to calc some inequalities

this a+b = n-c is very useful

We want to find the number of integer solutions for a, b, c such that:
1. a + b + c = n
2. 0 <= a, b, c <= l (where l is your limit)

The Approach (Iterative):

The idea is to iterate through all possible valid values for a (candies for the first child), then for each a, iterate through all valid values for b (candies for the second child). Once a and b are chosen, c is fixed (c = n - a - b). We then just need to ensure that this fixed c also satisfies 0 <= c <= l.

Deriving the Bounds for a:

We know:

• a + b + c = n
• 0 <= a <= l
• 0 <= b <= l
• 0 <= c <= l

Let's focus on a. We already have 0 <= a <= l.
We need to find the lower bound for a that ensures b and c can also be assigned valid values.

From b <= l and c <= l:
b + c <= 2 * l

Substitute b + c = n - a into the inequality:
n - a <= 2 * l

Rearrange to solve for a:
n - 2 * l <= a

Now, combine this with a >= 0 (since candies can't be negative):
a >= max(0, n - 2 * l)

And combine this with a <= l (from the original constraint):
a <= min(l, n) (The a <= n part is also true because a is a part of n, so a cannot be greater than n. Though a <= l is the stricter constraint if l < n, it's good to include a <= n for completeness.)

So, the range for a is max(0, n - 2 * l) <= a <= min(l, n).
This means, when iterating for a, you only need to go through values within this specific range.

Deriving the Bounds for b (Given a is chosen):

Now, assume a has been chosen. We need to find the valid range for b.
We know:

• a + b + c = n
• 0 <= b <= l
• 0 <= c <= l

From c = n - a - b, substitute into 0 <= c <= l:
0 <= n - a - b <= l

This gives us two inequalities:

1. n - a - b >= 0
n - a >= b
b <= n - a

2. n - a - b <= l
n - a - l <= b

Now, combine these with the original 0 <= b <= l:

• b >= 0 (original constraint)

• b >= n - a - l (from the second inequality above)
  So, b >= max(0, n - a - l)

• b <= l (original constraint)

• b <= n - a (from the first inequality above)
  So, b <= min(l, n - a)

Thus, for a given a, the range for b is max(0, n - a - l) <= b <= min(l, n - a).

Why these bounds are useful:

If you iterate a within its derived bounds, and then for each a, you iterate b within its derived bounds, the value of c = n - a - b is guaranteed to fall within 0 <= c <= l. This is because the derivation of a and b's bounds implicitly ensures that c will always be valid.

This approach would look something like this (conceptually):

count = 0
for a in range(max(0, n - 2 * l), min(l, n) + 1):
    for b in range(max(0, n - a - l), min(l, n - a) + 1):
        # At this point, c = n - a - b is automatically valid
        count += 1
return count

class Solution:
    def distributeCandies(self, n: int, limit: int) -> int:
        count = 0
        
        # Loop for 'a' (candies for the first child)
        for a in range(max(0, n - 2 * limit), min(limit, n) + 1):
            # For this fixed 'a', calculate the range of valid 'b' values
            b_min = max(0, n - a - limit)
            b_max = min(limit, n - a)
            
            # Instead of looping through all b values, directly count them
            if b_min <= b_max:
                # Number of valid b values = b_max - b_min + 1
                count += b_max - b_min + 1
        
        return count

complexity

limit^2 time
1 space

but for dfs, each traversal we have limit number of options so it is limit^3 time
1 space