Solution Approach

We use the binary search template with an inverted condition to find the maximum candies per child.

Defining the Infeasible Function:

We invert the problem to use the first_true_index template:

infeasible(v) = sum(pile // v for pile in candies) < k

This returns true when we cannot serve k children with v candies each.

Binary Search Setup:

• left = 1: Minimum candy amount to check
• right = max(candies) + 1: Upper bound (we extend by 1 to handle edge cases)
• first_true_index = 1: Default to 1 (meaning even 1 candy is infeasible → answer is 0)

Binary Search Template:

left, right = 1, max(candies) + 1
first_true_index = 1  # Default: infeasible starts at 1

while left <= right:
    mid = (left + right) // 2
    if infeasible(mid):  # Cannot serve k children
        first_true_index = mid
        right = mid - 1  # Find smaller infeasible value
    else:
        left = mid + 1  # mid is still feasible, try larger

return first_true_index - 1  # Maximum feasible = first infeasible - 1

Why This Works:

• When infeasible(mid) is true, we found where things break; try smaller values
• When infeasible(mid) is false, mid works; try larger values
• The answer is first_true_index - 1 (the last value before things became infeasible)

Time Complexity: O(n × log(max(candies))) where n is the length of the candies array.

Space Complexity: O(1) - only constant extra space used.

Example Walkthrough

Let's trace through with candies = [5, 8, 6] and k = 3.

Infeasible function: infeasible(v) = (5//v + 8//v + 6//v) < 3

Initialize:

• left = 1, right = max(5, 8, 6) + 1 = 9
• first_true_index = 1 (default)

Iteration 1: left = 1, right = 9

• mid = (1 + 9) // 2 = 5
• Portions: 5//5 + 8//5 + 6//5 = 1 + 1 + 1 = 3
• infeasible(5) = (3 < 3) → false (we CAN serve 3 children)
• left = 5 + 1 = 6

Iteration 2: left = 6, right = 9

• mid = (6 + 9) // 2 = 7
• Portions: 5//7 + 8//7 + 6//7 = 0 + 1 + 0 = 1
• infeasible(7) = (1 < 3) → true (we CANNOT serve 3 children)
• first_true_index = 7, right = 7 - 1 = 6

Iteration 3: left = 6, right = 6

• mid = (6 + 6) // 2 = 6
• Portions: 5//6 + 8//6 + 6//6 = 0 + 1 + 1 = 2
• infeasible(6) = (2 < 3) → true (we CANNOT serve 3 children)
• first_true_index = 6, right = 6 - 1 = 5

Termination: left = 6 > right = 5, exit loop

Result: first_true_index - 1 = 6 - 1 = 5

Verification:

• At v=5: portions = 3 ≥ 3 ✓ (feasible)
• At v=6: portions = 2 < 3 ✗ (infeasible)
• Maximum candies per child = 5

Time and Space Complexity

The time complexity is O(n × log M), where n is the length of the array candies, and M is the maximum value in the array candies. This complexity arises from:

• Binary search performs O(log M) iterations, as we search in the range [0, max(candies)]
• In each iteration, we calculate sum(x // mid for x in candies), which takes O(n) time to iterate through all elements

The space complexity is O(1), as the algorithm only uses a constant amount of extra space for variables l, r, and mid, regardless of the input size.

Learn more about how to find time and space complexity quickly.

Common Pitfalls

1. Using Wrong Binary Search Template Variant

A common mistake is using the standard "find maximum feasible" pattern instead of inverting to first_true_index.

Wrong approach:

while left < right:
    mid = (left + right + 1) // 2
    if feasible(mid):
        left = mid  # Wrong pattern
    else:
        right = mid - 1
return left

Correct approach (inverted condition):

first_true_index = 1  # Default
while left <= right:
    mid = (left + right) // 2
    if infeasible(mid):  # Cannot serve k children
        first_true_index = mid
        right = mid - 1
    else:
        left = mid + 1
return first_true_index - 1  # Maximum feasible

2. Division by Zero Error

Starting with left = 0 causes division by zero when mid = 0.

Solution: Always start with left = 1:

left = 1  # Not 0!
right = max(candies) + 1

3. Forgetting to Extend Upper Bound

If max(candies) itself is valid (all piles can contribute 1 portion of that size), we need to check beyond it to find where things become infeasible.

Solution: Use right = max(candies) + 1:

right = max(candies) + 1  # Not just max(candies)

4. Edge Case: More Children than Total Candies

If k > sum(candies), even giving 1 candy each is impossible.

Solution: The template handles this naturally - first_true_index will be 1, so answer is 0.