Minimum Time to Repair Cars - Practice Coding Problems

Minimum Time to Repair Cars - Problem

You are given an integer array ranks representing the ranks of some mechanics. ranks[i] is the rank of the i^th mechanic.

A mechanic with a rank r can repair n cars in r × n² minutes.

You are also given an integer cars representing the total number of cars waiting in the garage to be repaired.

Return the minimum time taken to repair all the cars.

Note: All the mechanics can repair the cars simultaneously.

Input & Output

Example 1 — Basic Case

$ Input: ranks = [4,2,3,1], cars = 10

› Output: 16

💡 Note: At time 16: mechanic 1 repairs √(16/4)=2 cars, mechanic 2 repairs √(16/2)=2√2≈2 cars, mechanic 3 repairs √(16/3)≈2 cars, mechanic 4 repairs √(16/1)=4 cars. Total = 2+2+2+4 = 10 cars exactly.

Example 2 — Single Mechanic

$ Input: ranks = [1], cars = 1

› Output: 1

💡 Note: Only one mechanic with rank 1 needs to repair 1 car. Time needed = 1 × 1² = 1 minute.

Example 3 — Multiple Cars per Mechanic

$ Input: ranks = [5,1,8], cars = 6

› Output: 16

💡 Note: At time 16: mechanic 1 repairs √(16/5)≈1 car, mechanic 2 repairs √(16/1)=4 cars, mechanic 3 repairs √(16/8)≈1 car. Total = 1+4+1 = 6 cars.

Constraints

1 ≤ ranks.length ≤ 10⁵
1 ≤ ranks[i] ≤ 100
1 ≤ cars ≤ 10⁶

Visualization

Tap to expand

Understanding the Visualization

Input

Mechanics with ranks [4,2,3,1] need to repair 10 cars

Process

Each mechanic can repair cars according to formula: time = rank × n²

Output

Find minimum time when all mechanics work together

Key Takeaway

🎯 Key Insight: Use binary search on answer space since the problem has monotonic property - if time T works, then T+1 also works

Asked in

G Google 35 a Amazon 28 M Microsoft 22 f Facebook 18

The key insight is to use binary search on the answer space instead of trying each time value. Since if we can repair all cars in time T, we can also do it in T+1, the problem has a monotonic property perfect for binary search. Best approach is binary search on answer with time complexity O(M × log(T)) where M is number of mechanics and T is the maximum possible time.

Common Approaches

Approach	Time	Space	Notes
✓ Linear Search on Time	O(T × M)	O(1)	Try every possible time starting from 1 until we find the minimum time to repair all cars
Binary Search on Answer	O(M × log(T))	O(1)	Use binary search to efficiently find the minimum time by searching the answer space

Linear Search on Time — Algorithm Steps

Start with time = 1
For each time, calculate total cars all mechanics can repair
Return the first time where total >= target cars

Visualization

Tap to expand

Step-by-Step Walkthrough

Start

Begin with time = 1

Calculate

For each time, sum cars all mechanics can repair

Check

If total >= target, return time; else increment

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <math.h>

long long solution(int* ranks, int ranksSize, int cars) {
    long long time = 1;
    while (1) {
        long long totalCars = 0;
        for (int i = 0; i < ranksSize; i++) {
            totalCars += (long long)sqrt(time / ranks[i]);
        }
        if (totalCars >= cars) {
            return time;
        }
        time++;
    }
}

int main() {
    char line[1000];
    fgets(line, sizeof(line), stdin);
    
    // Parse array
    int ranks[100];
    int ranksSize = 0;
    char* token = strtok(line + 1, ",]");
    while (token != NULL) {
        ranks[ranksSize++] = atoi(token);
        token = strtok(NULL, ",]");
    }
    
    int cars;
    scanf("%d", &cars);
    
    printf("%lld\n", solution(ranks, ranksSize, cars));
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(T × M)

T is the answer time (could be very large), M is number of mechanics

✓ Linear Growth

Space Complexity

O(1)

Only using constant extra variables

✓ Linear Space

68.4K Views

Medium Frequency

~25 min Avg. Time

1.8K Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Linear Search on Time — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler