Least time for a workshop to repair every car
A workshop has mechanics with ranks ranks[i]. A mechanic of rank r needs
r × n² minutes to repair n cars. All mechanics work at the same time. Return the
minimum number of minutes in which cars cars can all be repaired.
Examples
| Input | Output | Why |
|---|---|---|
ranks = [4, 2, 3, 1], cars = 10 | 16 | In 16 minutes: 2 + 2 + 2 + 4 = 10 cars (rank 4 does 2 in 16; rank 1 does 4 in 16). |
ranks = [5, 1, 8], cars = 6 | 16 | Rank 5: 1 car (5 min); rank 1: 4 cars (16 min); rank 8: 1 car (8 min). |
Constraints
- 1 ≤ ranks.length ≤ 10⁵
- 1 ≤ ranks[i] ≤ 100
- 1 ≤ cars ≤ 10⁶
Hints
Hint 1
Given t minutes, how many cars can a mechanic of rank r repair?
Hint 2
The largest n with r × n² ≤ t, which is ⌊√(t / r)⌋. Compute it with integers.
Hint 3
The total over all mechanics never falls as t grows. Search t in [1, min(ranks) × cars²].
Where people lose marks
- Using floating-point square roots without correcting them: an answer off by one minute fails the tests.
- Taking √(t) / r instead of √(t / r).
- Starting with hi = max(ranks) × cars², which works but wastes steps, or with a bound that fits in 32 bits, which does not.
Dry run on [4,2,3,1],10
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 / 8lo1hi100
Minutes from 1 to min(ranks) × 10² = 100, when the best mechanic alone would finish.
-
Step 2 / 8lo1mid50hi100
In 50 minutes: 3 + 5 + 4 + 7 = 19 cars, enough 10. 50 works, so the answer is 50 or smaller: hi = 50.
-
Step 3 / 8lo1mid25hi50
In 25 minutes: 2 + 3 + 2 + 5 = 12 cars, enough 10. 25 works, so the answer is 25 or smaller: hi = 25.
-
Step 4 / 8lo1mid13hi25
In 13 minutes: 1 + 2 + 2 + 3 = 8 cars, short of 10. 13 fails, so does everything below it: lo = 14.
-
Step 5 / 8lo14mid19hi25
In 19 minutes: 2 + 3 + 2 + 4 = 11 cars, enough 10. 19 works, so the answer is 19 or smaller: hi = 19.
-
Step 6 / 8lo14mid16hi19
In 16 minutes: 2 + 2 + 2 + 4 = 10 cars, enough 10. 16 works, so the answer is 16 or smaller: hi = 16.
-
Step 7 / 8lo14mid15hi16
In 15 minutes: 1 + 2 + 2 + 3 = 8 cars, short of 10. 15 fails, so does everything below it: lo = 16.
-
Step 8 / 8answer16
lo = hi = 16. In 16 minutes the workshop repairs 10 cars; in 15 only 8.
How to think about it
Asking "how should the cars be divided" is hard. Asking "is t minutes enough?" is easy: a mechanic
of rank r manages the largest n with r·n² ≤ t, which is
n = ⌊√⌊t / r⌋⌋, and they all work at once, so
cars(t) = Σ ⌊√⌊t / ranks[i]⌋⌋.
Each term is non-decreasing in t, so cars(t) ≥ cars is a monotone test and the answer
is its first true. The best mechanic alone repairs everything in min(ranks) × cars² minutes, which
is the upper bound: up to 10¹⁴, so use 64 bits.
The integer square root needs care. A floating-point sqrt of a number near
10¹⁴ can land one off in either direction, so correct it: decrease while n² > x, increase while
(n + 1)² ≤ x. Or use the language's exact integer root where there is one, such as
math.isqrt in Python.
Complexity. Time O(n log(min(ranks) × cars²)) · 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.
from math import isqrt
def repair_time(ranks, cars):
def enough(t):
return sum(isqrt(t // r) for r in ranks) >= cars # rank r: largest n with r*n*n <= t
lo, hi = 1, min(ranks) * cars * cars # the best mechanic alone
while lo < hi:
mid = (lo + hi) // 2
if enough(mid):
hi = mid
else:
lo = mid + 1
return lo#include <vector>
#include <cmath>
#include <algorithm>
static long long isqrt(long long x) { // exact integer square root
long long r = (long long)std::sqrt((double)x);
while (r * r > x) --r;
while ((r + 1) * (r + 1) <= x) ++r;
return r;
}
long long solve(const std::vector<int>& ranks, long long cars) {
auto enough = [&](long long t) {
long long done = 0;
for (long long r : ranks) {
done += isqrt(t / r);
if (done >= cars) return true;
}
return false;
};
long long lo = 1, hi = (long long)*std::min_element(ranks.begin(), ranks.end()) * cars * cars;
while (lo < hi) {
long long mid = lo + (hi - lo) / 2;
if (enough(mid)) hi = mid; else lo = mid + 1;
}
return lo;
}class Solution {
private long isqrt(long x) { // exact integer square root
long r = (long) Math.sqrt((double) x);
while (r * r > x) r--;
while ((r + 1) * (r + 1) <= x) r++;
return r;
}
public long repairTime(int[] ranks, int cars) {
long best = Long.MAX_VALUE;
for (int r : ranks) best = Math.min(best, r);
long lo = 1, hi = best * cars * cars;
while (lo < hi) {
long mid = lo + (hi - lo) / 2;
long done = 0;
for (int r : ranks) { done += isqrt(mid / r); if (done >= cars) break; }
if (done >= cars) hi = mid; else lo = mid + 1;
}
return lo;
}
}function repairTime(ranks, cars) {
// exact integer square root: correct the floating-point estimate
const isqrt = x => {
let r = Math.floor(Math.sqrt(x));
while (r * r > x) r--;
while ((r + 1) * (r + 1) <= x) r++;
return r;
};
const enough = t => {
let done = 0;
for (const r of ranks) { done += isqrt(Math.floor(t / r)); if (done >= cars) return true; }
return false;
};
let lo = 1, hi = Math.min(...ranks) * cars * cars; // at most 10^14: exact in a double
while (lo < hi) {
const mid = lo + Math.floor((hi - lo) / 2);
if (enough(mid)) hi = mid; else lo = mid + 1;
}
return lo;
}fn isqrt(x: i64) -> i64 { // exact integer square root
let mut r = (x as f64).sqrt() as i64;
while r * r > x {
r -= 1;
}
while (r + 1) * (r + 1) <= x {
r += 1;
}
r
}
fn solve(ranks: &[i64], cars: i64) -> i64 {
let enough = |t: i64| ranks.iter().map(|&r| isqrt(t / r)).sum::<i64>() >= cars;
let (mut lo, mut hi) = (1i64, ranks.iter().min().unwrap() * cars * cars);
while lo < hi {
let mid = lo + (hi - lo) / 2;
if enough(mid) { hi = mid } else { lo = mid + 1 }
}
lo
}-- exact integer square root: correct the floating-point estimate
isqrt :: Int -> Int
isqrt x = fixDown (floor (sqrt (fromIntegral x :: Double)))
where
fixDown r | r * r > x = fixDown (r - 1)
| otherwise = fixUp r
fixUp r | (r + 1) * (r + 1) <= x = fixUp (r + 1)
| otherwise = r
solve :: [Int] -> Int -> Int
solve ranks cars = go 1 (minimum ranks * cars * cars)
where
enough t = sum [isqrt (t `div` r) | r <- ranks] >= cars
go lo hi
| lo >= hi = lo
| enough mid = go lo mid
| otherwise = go (mid + 1) hi
where mid = lo + (hi - lo) `div` 2Variants to try
- Mechanics with cost r × n³: the same search with an integer cube root.
- Return how many cars each mechanic repairs: evaluate the terms at the answer, then trim the surplus from any mechanics.
Next problems
Smallest ship that clears the backlog in D days
When the answer is a number and "is X enough?" is easy to check, search over answers rather than over data.
Open the problem → Medium20 minThe slowest rate that clears every queue in time
At rate k a queue of p items takes ⌈p / k⌉ hours. The total only falls as k rises, so search for the smallest k that fits the deadline.
Open the problem → Medium20 minThe first day enough adjacent flowers are open
Fix a day and count how many runs of k open flowers it gives, greedily. More days never close a flower, so search the first day that gives m runs.
Open the problem →Write a solution and run it against the real test table.
Keep going
Smallest ship that clears the backlog in D days
When the answer is a number and "is X enough?" is easy to check, search over answers rather than over data.
Open the problem → Medium20 minThe slowest rate that clears every queue in time
At rate k a queue of p items takes ⌈p / k⌉ hours. The total only falls as k rises, so search for the smallest k that fits the deadline.
Open the problem → Medium20 minThe first day enough adjacent flowers are open
Fix a day and count how many runs of k open flowers it gives, greedily. More days never close a flower, so search the first day that gives m runs.
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.