Pseudo-code:

text
max_candies = max(candies)
for x from max_candies down to 1:
    count = 0
    for pile in candies:
        count += pile / x
    if count >= k:
        return x
return 0

Complexity Analysis: The time complexity is $O(M \cdot N)$, where $N$ is the length of the candies array and $M$ is the maximum value in candies (up to $10^7$). With $N = 10^5$ and $M = 10^7$, the total operations could reach $10^{12}$, which far exceeds the standard time limit of roughly $10^8$ operations per second. This approach results in a Time Limit Exceeded (TLE) error.

Core Insight for Maximum Candies Allocated to K Children

The key intuition is observing the monotonic nature of the "validity" function.

Let canAllocate(x) be a boolean function that returns true if it is possible to give x candies to k children, and false otherwise.

• If it is possible to give each child x candies, it is certainly possible to give them x - 1 candies (we simply have leftovers).
• If it is impossible to give each child x candies, it is certainly impossible to give them x + 1 candies (we cannot create matter).

This monotonicity allows us to discard half of the search space at every step. Instead of linearly scanning values, we can pick a middle value mid.

1. If canAllocate(mid) is true, then mid is a candidate solution, and we should try to find a larger valid number in the upper half [mid + 1, right].
2. If canAllocate(mid) is false, then mid is too large, and we must search in the lower half [left, mid - 1].

Visual Description: Imagine the number line from 0 to the maximum pile size. The function canAllocate(x) will return true for a prefix of this number line (e.g., 1, 2, 3... ans) and false for the suffix (ans+1 ... max). Our goal is to find the boundary where true transitions to false. Binary search efficiently converges on this boundary.

Execution Flow

Let candies = [5, 8, 6] and k = 3.

1. Initialization:

   • left = 1
   • right = 8 (max of candies)
   • ans = 0

2. Iteration 1:

   • mid = (1 + 8) / 2 = 4
   • Check mid = 4:
     • Pile 5 gives 5 / 4 = 1 child.
     • Pile 8 gives 8 / 4 = 2 children.
     • Pile 6 gives 6 / 4 = 1 child.
     • Total children = $1 + 2 + 1 = 4$.
   • Since $4 \ge 3$ (k), mid is valid.
   • ans = 4
   • left becomes 5.

3. Iteration 2:

   • left = 5, right = 8
   • mid = (5 + 8) / 2 = 6
   • Check mid = 6:
     • Pile 5 gives 0.
     • Pile 8 gives 1.
     • Pile 6 gives 1.
     • Total children = 2.
   • Since $2 < 3$, mid is invalid (too high).
   • right becomes 5.

4. Iteration 3:

   • left = 5, right = 5
   • mid = (5 + 5) / 2 = 5
   • Check mid = 5:
     • Pile 5 gives 1.
     • Pile 8 gives 1.
     • Pile 6 gives 1.
     • Total children = 3.
   • Since $3 \ge 3$, mid is valid.
   • ans = 5
   • left becomes 6.

5. Termination:

   • left = 6, right = 5. Loop terminates.
   • Return ans = 5.

Proof of Correctness

The correctness relies on the Monotonicity Property. Let $f(x)$ be the maximum number of children we can serve with $x$ candies each. $f(x) = \sum \lfloor \frac{candies[i]}{x} \rfloor$. Since $\lfloor \frac{A}{x} \rfloor$ is a non-increasing function with respect to $x$ (as $x$ increases, the result stays same or decreases), the sum $f(x)$ is also non-increasing. Therefore, the boolean predicate $P(x): f(x) \ge k$ is monotonic. Specifically, there exists a threshold $T$ such that for all $x \le T$, $P(x)$ is true, and for all $x > T$, $P(x)$ is false. Binary search is proven to find this threshold $T$ in logarithmic steps.

Reference Implementation

C++ Solution for LeetCode 2226

cpp
#include <vector>
#include <algorithm>
#include <numeric>

class Solution {
public:
    int maximumCandies(std::vector<int>& candies, long long k) {
        int left = 1;
        int right = 0;
        
        // Determine the search space upper bound
        for (int candy : candies) {
            right = std::max(right, candy);
        }
        
        int ans = 0;
        
        while (left <= right) {
            int mid = left + (right - left) / 2;
            
            // Check if 'mid' candies per child is feasible
            long long childrenServed = 0;
            for (int candy : candies) {
                childrenServed += candy / mid;
            }
            
            if (childrenServed >= k) {
                ans = mid;      // mid is a valid candidate
                left = mid + 1; // Try to find a larger valid amount
            } else {
                right = mid - 1; // mid is too large
            }
        }
        
        return ans;
    }
};

Java Solution for LeetCode 2226

java
class Solution {
    public int maximumCandies(int[] candies, long k) {
        int left = 1;
        int right = 0;
        
        // Determine the search space upper bound
        for (int candy : candies) {
            right = Math.max(right, candy);
        }
        
        int ans = 0;
        
        while (left <= right) {
            int mid = left + (right - left) / 2;
            
            // Check if 'mid' candies per child is feasible
            long childrenServed = 0;
            for (int candy : candies) {
                childrenServed += candy / mid;
            }
            
            if (childrenServed >= k) {
                ans = mid;      // mid is a valid candidate
                left = mid + 1; // Try to find a larger valid amount
            } else {
                right = mid - 1; // mid is too large
            }
        }
        
        return ans;
    }
}

Python Solution for LeetCode 2226

python
class Solution:
    def maximumCandies(self, candies: List[int], k: int) -> int:
        left, right = 1, max(candies)
        ans = 0
        
        while left <= right:
            mid = (left + right) // 2
            
            # Calculate total children that can be served with 'mid' candies
            children_served = sum(candy // mid for candy in candies)
            
            if children_served >= k:
                ans = mid       # mid is a valid candidate
                left = mid + 1  # Try to find a larger valid amount
            else:
                right = mid - 1 # mid is too large
                
        return ans

Q: Why do I get Time Limit Exceeded (TLE) with the correct logic?

• Mistake: Implementing an infinite loop in the binary search boundary updates. E.g., using left = mid without adjusting mid calculation to ceil.
• Why: If left = 1 and right = 2, mid becomes 1. If 1 is valid and you set left = mid, left remains 1, causing an infinite loop.
• Consequence: TLE. Use the standard left = mid + 1 and right = mid - 1 pattern for clarity and safety.