Max Candies to K Children
Ramayana — Sita's Diwali Distribution — Maximum Equal Share for Every Child
k बालकों को समान मिठाई — अधिकतम कितनी?। प्रत्येक ढेर से c टुकड़े — क्या k बालक मिलेंगे?॥
*Equal candies for k children — maximum how many? From each pile, c pieces — can k children be served?*
The Story
Given candy piles and k children, each child gets c consecutive candies from one pile (a pile of size s can give floor(s/c) children c candies). Maximize c such that all k children get exactly c candies.
For `candies=[5,8,6]`, k=3: answer=5. pile5 gives 1 child, pile8 gives 1 (8/5=1), pile6 gives 1. Total 3=k. At c=6: pile8 gives 1, pile5 gives 0, pile6 gives 1. Total 2<3. So max=5.
**Binary search on c:** - Range: [1, sum/k] (max possible c even if all from one pool) - For each c: total children = sum(floor(pile/c)) for all piles - Find maximum c such that total >= k
```java long sum=0; for (int c : candies) sum+=c; if (sum < k) return 0; int lo=1, hi=(int)(sum/k); while (lo < hi) { int mid=(lo+hi+1)/2; // Upper mid (maximize) long count=0; for (int c : candies) count+=c/mid; if (count >= k) lo=mid; // Feasible: try larger else hi=mid-1; } return lo; ```
Same template as bs-13 (maximize pattern) but even simpler feasibility check.
The Descending Candy Counter
Try c from max down to 1. Return first c where total children ≥ k. O(n × max_c).
public int maximumCandiesBruteForce(int[] candies, long k) {
int max = 0; for (int c : candies) max = Math.max(max, c);
for (int c = max; c >= 1; c--) {
long total = 0;
for (int p : candies) total += p/c;
if (total >= k) return c;
}
return 0;
}Sita's Maximum-Candy Binary Search
public int maximumCandies(int[] candies, long k) {
long sum = 0;
for (int c : candies) sum += c;
if (sum < k) return 0;
int lo = 1, hi = (int)(sum / k);
while (lo < hi) {
int mid = lo + (hi - lo + 1) / 2; // Upper mid
long count = 0;
for (int c : candies) count += c / mid;
if (count >= k) lo = mid;
else hi = mid - 1;
}
return lo;
}Step-by-Step Walkthrough
[10], k=3 sum=10. hi=10/3=3. lo=1,hi=3,mid=2: 10/2=5>=3 → lo=2 lo=2,hi=3,mid=3: 10/3=3>=3 → lo=3 lo==hi=3 → return 3 ✅ (3 children each get 3 candies from the single pile of 10)
Deep Insight
**Maximize pattern reminder:** feasible → lo=mid (upper mid prevents infinite loop). Return lo. **Minimize pattern (bs-11):** feasible → hi=mid (standard mid). Return lo.
**`hi = sum/k`:** Maximum possible answer — if we pool all candies and divide by k, that's the upper bound. Any c larger would require more than sum total candies.
**floor division `c/mid`:** Each pile of size c gives floor(c/mid) children exactly mid candies.
Complexity Analysis
| Approach | Time | Space | Note |
|---|---|---|---|
| Brute Force | O(n × max) | O(1) | Try each c |
| Optimal | O(n log(sum/k)) | O(1) | Binary search on [1, sum/k] + O(n) feasibility check |
Pattern Recognition
✅ Maximize c such that sum(floor(pile/c)) >= k ✅ Upper mid (maximize pattern) ✅ Feasible: lo=mid; Infeasible: hi=mid-1 ✅ Early exit: if sum < k return 0 **LeetCode Trigger Phrases:** → "maximum candies" per child → Maximize the minimum allocation → Floor-division feasibility check
Bhagavad Gita 3.13
यज्ञशिष्टाशिनः सन्तो मुच्यन्ते सर्वकिल्बिषैः।
Those who eat the remnants of sacrifice are freed from all sins.
Connection: Fair distribution — giving each child the maximum equal share — is a form of sacred distribution. The algorithm finds the maximum c such that every child receives their due, with perhaps some candy left over in each pile. Like prasad distributed after a yajna, the goal is maximum equal sharing. Binary search finds this point of optimal generosity: as much as possible, but equally for all.