NeetCode #937LC-2929MediumMath & Geometry
← Back to All Problems#937 · #2929 · Distribute Candies Among Children II(给小朋友们分糖果 II)
📌 Problem Statement & Constraints
Given two positive integers
n and limit, count the ways to distribute n identical candies among 3 children so that no child receives more than limit. Constraints: 1 <= n <= 10^5, 1 <= limit <= 10^5.💡 Core Algorithmic Approaches
- Enumerate the number
agiven to the first child, from 0 tomin(limit, n). - The remaining
rem = n - ais split between two children with0 <= b, c <= limitandb + c = rem. - For a fixed
a,branges over[max(0, rem - limit), min(limit, rem)], contributinghi - lo + 1ways. - Summing over all
agives the answer in O(min(limit, n)) time.
💻 Benchmark Python3 Implementation
class Solution:
def distributeCandies(self, n: int, limit: int) -> int:
res = 0
for a in range(min(limit, n) + 1):
rem = n - a
if rem > 2 * limit: # even b = c = limit is not enough
continue
lo = max(0, rem - limit)
hi = min(limit, rem)
if lo <= hi:
res += hi - lo + 1
return res⚡ Complexity Deep Dive
⏱️ Time Complexity
O(min(limit, n)): a single loop over the first child's share.
💾 Space Complexity
O(1): constant state.
⚠️ Interview Pitfalls & Follow-ups
- Triple-nesting the loops over
a, b, c: O(n^3) times out; the third value is determined by the first two. - Setting
b's lower bound to 0: whenrem > limit,bmust be at leastrem - limitso thatcstays withinlimit. - Omitting the
rem > 2 * limitskip: thelo <= hicheck already handles it, but the early skip is clearer and faster. - Forgetting that
acan be 0: the enumeration starts at 0, since a child may receive nothing.
⚡
Test muscle memory on this topic via 3-Layer Flashcards
Active Recall: Mentally formulate Prompt ➔ Math Derivation ➔ Benchmark Implementation in 3 minutes.