⚡Flashcard Drill➔
NeetCode #278LC-2226MediumBinary Search
← Back to All Problems

#278 · #2226 · Maximum Candies Allocated to K Children(分配给 K 个孩子的最大糖果数)

📌 Problem Statement & Constraints

You are given a 0-indexed integer array candies where candies[i] is the number of candies in the i-th pile, and an integer k. Each child receives candies from a single pile, and piles cannot be split across children. Return the maximum number of candies each child can get. Constraints: 1 <= candies.length <= 10^5, 1 <= candies[i] <= 10^7, 1 <= k <= 10^12.

💡 Core Algorithmic Approaches

  1. Binary search on the answer: "can each of the k children get at least c candies" is monotone in c.
  2. For a given c, the number of children that can be served is sum(pile // c).
  3. The answer is feasible when that count is at least k. Use the upper-biased midpoint to maximise.
  4. If the total number of candies is less than k, the answer is 0 -- check this before the search.

💻 Benchmark Python3 Implementation

class Solution:
    def maximumCandies(self, candies: List[int], k: int) -> int:
        if sum(candies) < k:
            return 0                   # impossible to give everyone one
        lo, hi = 1, max(candies)
        while lo < hi:
            mid = (lo + hi + 1) // 2   # upper-biased: maximise
            children = sum(c // mid for c in candies)
            if children >= k:
                lo = mid               # feasible -> try larger
            else:
                hi = mid - 1
        return lo

⚡ Complexity Deep Dive

⏱️ Time Complexity
O(n log(max(candies))): each predicate is O(n).
💾 Space Complexity
O(1): a few scalars.

⚠️ Interview Pitfalls & Follow-ups

  • Using the lower-biased midpoint with lo = mid: infinite loop; the upper bias is required for maximisation.
  • Forgetting the feasibility check: if the total is less than k, the binary search would still return 1 (since mid = 1 always gives sum(candies) >= k... which is false), so the guard is needed.
  • Allowing a pile to be split between children: each child takes from exactly one pile, which is why the floor division is used.
  • Using children == k instead of >= k: serving more children than required is fine; the surplus is simply unused.
⚡
Test muscle memory on this topic via 3-Layer Flashcards
Active Recall: Mentally formulate Prompt ➔ Math Derivation ➔ Benchmark Implementation in 3 minutes.
🎯 Drill This Card Now➔

🧩 Related Binary Search Problems