⚡Flashcard Drill➔
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

  1. Enumerate the number a given to the first child, from 0 to min(limit, n).
  2. The remaining rem = n - a is split between two children with 0 <= b, c <= limit and b + c = rem.
  3. For a fixed a, b ranges over [max(0, rem - limit), min(limit, rem)], contributing hi - lo + 1 ways.
  4. Summing over all a gives 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: when rem > limit, b must be at least rem - limit so that c stays within limit.
  • Omitting the rem > 2 * limit skip: the lo <= hi check already handles it, but the early skip is clearer and faster.
  • Forgetting that a can 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.
🎯 Drill This Card Now➔

🧩 Related Math & Geometry Problems