✔️ Binary Search | Python | C++ | Java | JS | C# | Go
Support By Upvoting the Post ⬆️IntuitionThe problem asks for the minimum time to repair all cars using mechanics with different ranks, where a mechanic with ran
# Support By Upvoting the Post ⬆️

# Intuition
The problem asks for the minimum time to repair all cars using mechanics with different ranks, where a mechanic with rank `r` takes `r * n²` minutes to repair `n` cars. The key insight is that we can use `binary search` to find this minimum time efficiently.
If we have a specific time `t`, we can determine how many cars each mechanic can repair within that time. Then we can check if all cars can be repaired within time `t`. This allows us to perform a `binary search` on the possible time values.

# Approach
1. Define a search range:
    - Minimum time: 1
    - Maximum time: The time it would take if the fastest mechanic repairs all cars alone


2. For each potential time `t` in our binary search:

    - Calculate how many cars each mechanic can repair in time `t`
    - If a mechanic with rank `r` can repair `n` cars in time `t`, then: `r * n² ≤ t`, so `n = floor(sqrt(t/r))`
    - Sum up the total number of cars all mechanics can repair
    - If this sum is at least equal to the required number of cars, time `t` is feasible


3. Use binary search to find the minimum feasible time

# Complexity
- Time complexity: `O(m * log(r * n * n))`, where `m` is the number of mechanics (length of ranks), `n` is the number of cars, and `r` is the minimum rank. 

- Space complexity: `O(1)`

# Code
```python3 []
class Solution:
    def repairCars(self, ranks: List[int], cars: int) -> int:
        left = 1
        right = min(ranks) * cars * cars 
        
        def can_repair_all(time):
            total_cars_repaired = 0
            for rank in ranks:
                cars_repaired = int((time / rank) ** 0.5)
                total_cars_repaired += cars_repaired
                if total_cars_repaired >= cars:
                    return True
            return False
        
        while left < right:
            mid = (left + right) // 2
            if can_repair_all(mid):
                right = mid
            else:
                left = mid + 1
                
        return left
        
```
```cpp []
class Solution {
public:
    long long repairCars(vector<int>& ranks, int cars) {
        long long left = 1, right = (long long)*min_element(ranks.begin(), ranks.end()) * cars * cars;
        
        auto can_repair_all = [&](long long time) {
            long long total_cars_repaired = 0;
            for (int rank : ranks) {
                total_cars_repaired += sqrt(time / rank);
                if (total_cars_repaired >= cars) return true;
            }
            return false;
        };
        
        while (left < right) {
            long long mid = (left + right) / 2;
            if (can_repair_all(mid)) {
                right = mid;
            } else {
                left = mid + 1;
            }
        }
        
        return left;
    }
};
```
```java []
class Solution {
    public long repairCars(int[] ranks, int cars) {
        long left = 1, right = (long) Arrays.stream(ranks).min().getAsInt() * cars * cars;

        while (left < right) {
            long mid = (left + right) / 2;
            if (canRepairAll(ranks, cars, mid)) {
                right = mid;
            } else {
                left = mid + 1;
            }
        }

        return left;
    }

    private boolean canRepairAll(int[] ranks, int cars, long time) {
        long totalCarsRepaired = 0;
        for (int rank : ranks) {
            totalCarsRepaired += Math.sqrt(time / rank);
            if (totalCarsRepaired >= cars) return true;
        }
        return false;
    }
}
```
```javascript []
var repairCars = function(ranks, cars) {
    let left = 1, right = Math.min(...ranks) * cars * cars;

    const canRepairAll = (time) => {
        let totalCarsRepaired = 0;
        for (let rank of ranks) {
            totalCarsRepaired += Math.floor(Math.sqrt(time / rank));
            if (totalCarsRepaired >= cars) return true;
        }
        return false;
    };

    while (left < right) {
        let mid = Math.floor((left + right) / 2);
        if (canRepairAll(mid)) {
            right = mid;
        } else {
            left = mid + 1;
        }
    }

    return left;
};
```
```csharp []
public class Solution {
    public long RepairCars(int[] ranks, int cars) {
        long left = 1, right = (long)ranks.Min() * cars * cars;

        while (left < right) {
            long mid = (left + right) / 2;
            if (CanRepairAll(ranks, cars, mid)) {
                right = mid;
            } else {
                left = mid + 1;
            }
        }

        return left;
    }

    private bool CanRepairAll(int[] ranks, int cars, long time) {
        long totalCarsRepaired = 0;
        foreach (int rank in ranks) {
            totalCarsRepaired += (long)Math.Sqrt(time / rank);
            if (totalCarsRepaired >= cars) return true;
        }
        return false;
    }
}
```
```go []
func repairCars(ranks []int, cars int) int64 {
	left, right := int64(1), int64(ranks[0])*int64(cars)*int64(cars)

	canRepairAll := func(time int64) bool {
		totalCarsRepaired := int64(0)
		for _, rank := range ranks {
			totalCarsRepaired += int64(math.Sqrt(float64(time / int64(rank))))
			if totalCarsRepaired >= int64(cars) {
				return true
			}
		}
		return false
	}

	for left < right {
		mid := (left + right) / 2
		if canRepairAll(mid) {
			right = mid
		} else {
			left = mid + 1
		}
	}

	return left
}
```
---
![upvote.png](https://assets.leetcode.com/users/images/c93dcf48-bd2b-4dda-a244-e970d16d341e_1742098075.4041057.png)

['Binary Search', 'Python', 'C++', 'Java', 'Go', 'Python3', 'JavaScript', 'C#']