Minimum Time to Repair Cars — Medium Problem & Solution

A mechanic with rank r needs r k² minutes to repair k cars. All mechanics work simultaneously**.

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 <= 100
1 <= ranks[i] <= 100
1 <= cars <= 1000

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 1 to max(ranks) * cars², which is certainly enough time.
For a candidate t, sum floor(sqrt(t / r)) over the ranks, stopping early once the total reaches cars.
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 sqrt can 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 no math.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 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#, C++, Go, Java, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 667 arrays problems · the whole catalogue