Minimum Time to Repair Cars — Solution in Python, Java & C++
Minimum Time to Repair Cars solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A medium problem.
Minimum Time to Repair Cars is a medium coding problem on arrays, greedy and binary search, asked in Amazon, Google and Flipkart interviews.
- Difficulty: Medium
- Topics: Arrays, Greedy, Binary Search
- Asked at: Amazon, Google, Flipkart
- Time limit: 2 s
- Memory limit: 256 MB
- Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
Problem statement
A mechanic with rank r needs r * k² minutes to repair k cars. All mechanics work simultaneously.
Given the ranks and the number of cars to repair, return the minimum number of minutes until every car is done.
Example 1
Input: ranks = [4,2,3,1], cars = 10
Output: 16
Explanation: In 16 minutes the ranks repair 2, 2, 2 and 4 cars — ten in total.
Example 2
Input: ranks = [5,1,8], cars = 6
Output: 16
Explanation: 1 + 4 + 1 = 6 cars in 16 minutes.
Example 3
Input: ranks = [1], cars = 3
Output: 9
Constraints
1 <= ranks.length <= 1001 <= ranks[i] <= 1001 <= cars <= 1000
Hints for Minimum Time to Repair Cars
Hint 1
If
tminutes are enough, so is any larger time — the feasibility test is monotone, which is the signal for binary search.Hint 2
In
tminutes a mechanic of rankrfinishesfloor(sqrt(t / r))cars.Hint 3
Binary search the smallest
twhose total reachescars.
How to solve Minimum Time to Repair Cars
Binary search on the answer. Checking a candidate time is a single pass: each mechanic's throughput at time t is floor(sqrt(t / r)), and the question is whether the throughputs sum to at least cars.
Approach
- Set the search range from
1tomax(ranks) * cars², which is certainly enough time. - For a candidate
t, sumfloor(sqrt(t / r))over the ranks, stopping early once the total reachescars. - Shrink the range towards the smallest feasible
t.
Why it works
The throughput of each mechanic is non-decreasing in t, so feasibility is monotone and the boundary is exactly the answer. The upper bound works because a single mechanic of the worst rank could do all the cars in that time.
Complexity
- Time —
O(n log(max rank · cars²)) - Space —
O(1)
Pitfalls
- Floating-point
sqrtcan land one off near a perfect square; an integer square root by binary search avoids the question entirely — and the judge's C harness has nomath.h. - The upper bound
max(ranks) * cars²reaches 10⁸ here; at LeetCode's real limits it needs 64 bits. - Dividing before the square root (
sqrt(t / r)) is correct because the floor of the quotient never overshoots.
Reference solution
Python
from typing import List
def repairCars(ranks: List[int], cars: int) -> int:
def isqrt(v: int) -> int:
lo, hi = 0, 100000
while lo < hi:
mid = (lo + hi + 1) // 2
if mid * mid <= v:
lo = mid
else:
hi = mid - 1
return lo
lo, hi = 1, max(ranks) * cars * cars
while lo < hi:
mid = (lo + hi) // 2
done = 0
for r in ranks:
done += isqrt(mid // r)
if done >= cars:
break
if done >= cars:
hi = mid
else:
lo = mid + 1
return loJava
public static int repairCars(int[] ranks, int cars) {
long lo = 1, hi = 0;
for (int r : ranks) hi = Math.max(hi, (long) r * cars * cars);
while (lo < hi) {
long mid = (lo + hi) / 2;
long done = 0;
for (int r : ranks) {
done += isqrtRepair(mid / r);
if (done >= cars) break;
}
if (done >= cars) hi = mid;
else lo = mid + 1;
}
return (int) lo;
}
static long isqrtRepair(long v) {
long lo = 0, hi = 100000;
while (lo < hi) {
long mid = (lo + hi + 1) / 2;
if (mid * mid <= v) lo = mid;
else hi = mid - 1;
}
return lo;
}C++
static long long isqrtRepair(long long v) {
long long lo = 0, hi = 100000;
while (lo < hi) {
long long mid = (lo + hi + 1) / 2;
if (mid * mid <= v) lo = mid;
else hi = mid - 1;
}
return lo;
}
int repairCars(vector<int>& ranks, int cars) {
long long lo = 1, hi = 0;
for (int r : ranks) hi = max(hi, (long long) r * cars * cars);
while (lo < hi) {
long long mid = (lo + hi) / 2;
long long done = 0;
for (int r : ranks) {
done += isqrtRepair(mid / r);
if (done >= cars) break;
}
if (done >= cars) hi = mid;
else lo = mid + 1;
}
return (int) lo;
}JavaScript
var repairCars = function(ranks, cars) {
var isqrt = function(v) {
var lo = 0, hi = 100000;
while (lo < hi) {
var mid = Math.floor((lo + hi + 1) / 2);
if (mid * mid <= v) lo = mid;
else hi = mid - 1;
}
return lo;
};
var lo = 1, hi = 0;
for (var i = 0; i < ranks.length; i++) {
var t = ranks[i] * cars * cars;
if (t > hi) hi = t;
}
while (lo < hi) {
var mid = Math.floor((lo + hi) / 2);
var done = 0;
for (var j = 0; j < ranks.length; j++) {
done += isqrt(Math.floor(mid / ranks[j]));
if (done >= cars) break;
}
if (done >= cars) hi = mid;
else lo = mid + 1;
}
return lo;
};Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.
All 1199 arrays problems · the whole catalogue
Learn the technique: Arrays · Greedy Algorithms