Longest time n machines can run on shared batteries
Hard · Target 30 minutes · Binary search · Type asked atGoogleCitadel
Jane Street
You have n machines and a list of batteries; battery i holds batteries[i]
minutes of charge. Each machine needs exactly one battery at a time. At any whole minute you may swap batteries
between machines instantly, and a battery's remaining charge stays with it. Return the largest number of minutes
for which all n machines can run at the same time.
Examples
| Input | Output | Why |
|---|---|---|
n = 2, batteries = [3, 3, 3] | 4 | 9 minutes of charge for two machines: 4 minutes each, with swaps. |
n = 2, batteries = [1, 1, 1, 1] | 2 | |
n = 2, batteries = [100, 1] | 1 | The big battery cannot power two machines at once. |
Constraints
- 1 ≤ n ≤ batteries.length ≤ 10⁵
- 1 ≤ batteries[i] ≤ 10⁹
Hints
Hint 1
Fix a target t. How much of battery i can actually be used in t minutes?
Hint 2
At most min(batteries[i], t): one battery can power only one machine at a time.
Hint 3
The machines need n·t minutes of charge, so t is achievable when Σ min(b, t) ≥ n·t, and it then turns out to be enough as well. Search the last t that passes, up to sum / n.
Where people lose marks
- Testing Σ b ≥ n · t without the cap: [100, 1] with n = 2 would claim 50 minutes.
- Overflowing n · t or the sum in 32 bits.
- Rounding the midpoint down while setting lo = mid.
Dry run on 3,[10,10,3,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 / 6lo0hi9
28 minutes of charge for 3 machines, so no more than 9 minutes. Search for the last t that passes; mid rounds up.
-
Step 2 / 6lo0mid5hi9
t = 5: usable charge 5 + 5 + 3 + 5 = 18; needed 3 × 5 = 15. Enough. 5 works, so the answer is 5 or larger: lo = 5.
-
Step 3 / 6lo5mid7hi9
t = 7: usable charge 7 + 7 + 3 + 5 = 22; needed 3 × 7 = 21. Enough. 7 works, so the answer is 7 or larger: lo = 7.
-
Step 4 / 6lo7mid8hi9
t = 8: usable charge 8 + 8 + 3 + 5 = 24; needed 3 × 8 = 24. Enough. 8 works, so the answer is 8 or larger: lo = 8.
-
Step 5 / 6lo8mid9hi9
t = 9: usable charge 9 + 9 + 3 + 5 = 26; needed 3 × 9 = 27. Not enough. 9 fails, so does everything above it: hi = 8.
-
Step 6 / 6answer8
lo = hi = 8: all 3 machines run for 8 minutes.
How to think about it
Ask whether all machines can run for t minutes. They need n · t machine-minutes
of charge in total. A battery can supply at most t of its charge, since it powers only one machine
in any minute, so the usable charge is Σ min(batteries[i], t). The condition
Σ min(batteries[i], t) ≥ n · t
is necessary. It is also sufficient: lay the capped charges end to end and cut the line into n
lanes of length t. A battery's stretch is at most t long, so it never covers the same
minute in two lanes, and each lane is one machine's timetable.
If t passes, so does every smaller t: a timetable that runs every machine for
t minutes, stopped a minute early, runs them for t − 1. So search the last passing t in [0, ⌊Σ b / n⌋], midpoint rounded
up. The sum reaches 10¹⁴: use 64 bits.
There is a greedy answer too: while the largest battery exceeds the average share, it can run one machine for the whole time alone, so remove it and that machine; then the rest pool perfectly and the answer is their sum divided by the machines left. It is the oracle these tests are checked against.
Complexity. Time O(m log(Σb / n)) · 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_run_time(n, batteries):
lo, hi = 0, sum(batteries) // n # 0 always works
while lo < hi:
mid = (lo + hi + 1) // 2 # round up
usable = sum(min(b, mid) for b in batteries) # a battery gives at most mid
if usable >= n * mid:
lo = mid
else:
hi = mid - 1
return lo#include <vector>
#include <numeric>
#include <algorithm>
long long solve(long long n, const std::vector<int>& batteries) {
long long lo = 0, hi = std::accumulate(batteries.begin(), batteries.end(), 0LL) / n;
while (lo < hi) {
long long mid = lo + (hi - lo + 1) / 2; // round up
long long usable = 0;
for (long long b : batteries) usable += std::min(b, mid); // at most mid per battery
if (usable >= n * mid) lo = mid; else hi = mid - 1;
}
return lo;
}class Solution {
public long maxRunTime(int n, int[] batteries) {
long sum = 0;
for (int b : batteries) sum += b;
long lo = 0, hi = sum / n;
while (lo < hi) {
long mid = lo + (hi - lo + 1) / 2; // round up
long usable = 0;
for (int b : batteries) usable += Math.min(b, mid); // at most mid per battery
if (usable >= n * mid) lo = mid; else hi = mid - 1;
}
return lo;
}
}function maxRunTime(n, batteries) {
let lo = 0, hi = Math.floor(batteries.reduce((s, b) => s + b, 0) / n); // < 2^53
while (lo < hi) {
const mid = lo + Math.ceil((hi - lo) / 2); // round up
let usable = 0;
for (const b of batteries) usable += Math.min(b, mid); // at most mid per battery
if (usable >= n * mid) lo = mid; else hi = mid - 1;
}
return lo;
}fn solve(n: i64, batteries: &[i64]) -> i64 {
let (mut lo, mut hi) = (0i64, batteries.iter().sum::<i64>() / n);
while lo < hi {
let mid = lo + (hi - lo + 1) / 2; // round up
let usable: i64 = batteries.iter().map(|&b| b.min(mid)).sum(); // at most mid each
if usable >= n * mid { lo = mid } else { hi = mid - 1 }
}
lo
}solve :: Int -> [Int] -> Int
solve n batteries = go 0 (sum batteries `div` n)
where
usable t = sum [min b t | b <- batteries] -- at most t from each battery
go lo hi
| lo >= hi = lo
| usable mid >= n * mid = go mid hi
| otherwise = go lo (mid - 1)
where mid = lo + (hi - lo + 1) `div` 2 -- round upVariants to try
- Swaps allowed at any real moment: the same answer, since the bound Σ min(b, t) ≥ n·t is still the only constraint.
- Each machine has its own draw rate: the cap becomes per machine, and the problem turns into a flow question.
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 → Medium20 minThe largest equal share for k people
A pile of p cut into shares of x yields ⌊p / x⌋ shares. Bigger shares mean fewer of them: search for the last x that still gives k.
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 → Medium20 minThe largest equal share for k people
A pile of p cut into shares of x yields ⌊p / x⌋ shares. Bigger shares mean fewer of them: search for the last x that still gives k.
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.