The largest equal share for k people
You have piles of sweets, piles[i] in pile i. You may split any pile into smaller piles,
but you may not merge piles. Give each of k children exactly one pile, all of the same size
x; some sweets may be left over. Return the largest possible x, or 0 if every child
cannot get even one sweet.
Examples
| Input | Output | Why |
|---|---|---|
piles = [5, 8, 6], k = 3 | 5 | Shares of 5: one from each pile. Shares of 6 give only two. |
piles = [2, 5], k = 11 | 0 | There are only 7 sweets. |
piles = [4, 7, 5], k = 4 | 3 | 1 + 2 + 1 = 4 shares of 3. |
Constraints
- 1 ≤ piles.length ≤ 10⁵
- 1 ≤ piles[i] ≤ 10⁷
- 1 ≤ k ≤ 10¹²
Hints
Hint 1
For a share size x, how many shares can pile i provide?
Hint 2
⌊piles[i] / x⌋, because shares cannot combine sweets from two piles. Sum over the piles.
Hint 3
Larger x never gives more shares, so "at least k shares" holds up to some x and fails after it. Search for the last x that holds; if even x = 1 fails, the answer is 0.
Where people lose marks
- Dividing by zero when the search reaches x = 0: treat 0 as feasible without computing shares(0).
- Holding k or the share count in 32 bits: k reaches 10¹².
- Returning 1 when the total is smaller than k.
Dry run on [5,8,6,11],5
Read it one frame at a time, the way you would trace the code on paper in an interview. Each frame shows the state after the step it describes.
-
Step 1 / 6lo0hi11
Sizes from 0 (always possible: nobody gets anything) to the largest pile, 11. Search for the last size that gives 5 shares; mid rounds up.
-
Step 2 / 6lo0mid6hi11
Shares of 6: 0 + 1 + 1 + 1 = 3, fewer than 5. 6 fails, so does everything above it: hi = 5.
-
Step 3 / 6lo0mid3hi5
Shares of 3: 1 + 2 + 2 + 3 = 8, enough 5. 3 works, so the answer is 3 or larger: lo = 3.
-
Step 4 / 6lo3mid4hi5
Shares of 4: 1 + 2 + 1 + 2 = 6, enough 5. 4 works, so the answer is 4 or larger: lo = 4.
-
Step 5 / 6lo4mid5hi5
Shares of 5: 1 + 1 + 1 + 2 = 5, enough 5. 5 works, so the answer is 5 or larger: lo = 5.
-
Step 6 / 6answer5
lo = hi = 5. Shares of 5 give 5; shares of 6 give 3.
How to think about it
Fix a share size x. A pile of p sweets yields ⌊p / x⌋ shares and the
leftover is wasted, because a share cannot combine sweets from two piles. So
shares(x) = Σ ⌊piles[i] / x⌋,
and the question for a fixed x is whether shares(x) ≥ k. Bigger shares never
increase the count, so the test is true for small x and false beyond some point: search for the
last true, rounding the midpoint up.
The range needs one extra thought. If even shares of 1 do not reach k (fewer sweets than children)
the answer is 0, which sits outside the natural range [1, max(piles)]. Searching
[0, max(piles)] and treating 0 as always feasible handles it without a special case.
Compare the eating-rate problem: there ⌈p / k⌉ hours per pile and we searched for the smallest rate; here ⌊p / x⌋ shares per pile and we search for the largest size. Same arithmetic, opposite direction, and the direction decides which way the midpoint rounds.
Complexity. Time O(n log max(piles)) · Space O(1)
The solution, in six languages
Each one is compiled and run against the test table before it is published. Java is reviewed by hand.
def max_share(piles, k):
lo, hi = 0, max(piles) # size 0 always "works": nobody gets anything
while lo < hi:
mid = (lo + hi + 1) // 2 # round up, so mid >= 1
if sum(p // mid for p in piles) >= k:
lo = mid # big enough count: try larger shares
else:
hi = mid - 1
return lo#include <vector>
#include <algorithm>
long long solve(const std::vector<int>& piles, long long k) {
long long lo = 0, hi = *std::max_element(piles.begin(), piles.end()); // 0 always works
while (lo < hi) {
long long mid = lo + (hi - lo + 1) / 2; // round up, so mid >= 1
long long count = 0;
for (long long p : piles) count += p / mid;
if (count >= k) lo = mid; else hi = mid - 1;
}
return lo;
}class Solution {
public int maxShare(int[] piles, long k) {
int lo = 0, hi = 0; // 0 always works
for (int p : piles) hi = Math.max(hi, p);
while (lo < hi) {
int mid = lo + (hi - lo + 1) / 2; // round up, so mid >= 1
long count = 0;
for (int p : piles) count += p / mid;
if (count >= k) lo = mid; else hi = mid - 1;
}
return lo;
}
}function maxShare(piles, k) {
let lo = 0, hi = Math.max(...piles); // size 0 always works
while (lo < hi) {
const mid = lo + Math.ceil((hi - lo) / 2); // round up, so mid >= 1
let count = 0;
for (const p of piles) count += Math.floor(p / mid);
if (count >= k) lo = mid; else hi = mid - 1;
}
return lo;
}fn solve(piles: &[i64], k: i64) -> i64 {
let (mut lo, mut hi) = (0i64, *piles.iter().max().unwrap()); // 0 always works
while lo < hi {
let mid = lo + (hi - lo + 1) / 2; // round up, so mid >= 1
let count: i64 = piles.iter().map(|&p| p / mid).sum();
if count >= k { lo = mid } else { hi = mid - 1 }
}
lo
}solve :: [Int] -> Int -> Int
solve piles k = go 0 (maximum piles) -- size 0 always works
where
go lo hi
| lo >= hi = lo
| sum [p `div` mid | p <- piles] >= k = go mid hi
| otherwise = go lo (mid - 1)
where mid = lo + (hi - lo + 1) `div` 2 -- round up, so mid >= 1Variants to try
- Cut ropes into k pieces of equal length, lengths real: the same search over reals, or over integers scaled to the precision required.
- Each child must get sweets from a single original pile: that is already the rule here.
Next problems
Spread m items to maximise the closest pair
Guess a spacing d; place items greedily, each at the first position at least d past the last. If m fit, a wider spacing might too. Search the last d that fits.
Open the problem → Hard30 minLongest time n machines can run on shared batteries
Can all n machines run for t minutes? A battery can contribute at most t of its charge, so the test is Σ min(b, t) ≥ n·t. Search the last t that passes.
Open the problem → Easy10 minFind a value in a sorted array
The search every other binary search is built on: halve a closed range until the value is found or the range is empty.
Open the problem →Write a solution and run it against the real test table.
Keep going
Spread m items to maximise the closest pair
Guess a spacing d; place items greedily, each at the first position at least d past the last. If m fit, a wider spacing might too. Search the last d that fits.
Open the problem → Hard30 minLongest time n machines can run on shared batteries
Can all n machines run for t minutes? A battery can contribute at most t of its charge, so the test is Σ min(b, t) ≥ n·t. Search the last t that passes.
Open the problem → Easy10 minFind a value in a sorted array
The search every other binary search is built on: halve a closed range until the value is found or the range is empty.
Open the problem → Binary searchThe pattern behind it
Search the answer, not the array: halve a monotone predicate until one candidate is left.
Read the pattern →Preparing for a real process? Quant interview preparation, or book a free 20-minute call.