Binary Search on Time 💋
IntuitionThe problem can be solved using binary search on the minimum time required to repair all cars. The idea is to check if a given time mid is sufficient t
# Intuition
The problem can be solved using binary search on the minimum time required to repair all cars. The idea is to check if a given time `mid` is sufficient to repair all cars, and adjust the search range accordingly.

# Approach
1. **Binary Search on Time:**  
   - The minimum possible time is `1`, and the maximum possible time is when the slowest mechanic repairs all cars.
   - We use binary search between this range to find the minimum required time.

2. **Checking Validity of a Given Time:**  
   - For a given time `mid`, check if it is possible to repair `cars` using the given ranks.
   - A mechanic with rank `r` can repair at most `floor(sqrt(mid / r))` cars.
   - Sum up the cars repaired by all mechanics and check if it meets or exceeds `cars`.

3. **Binary Search Logic:**  
   - If a time `mid` is sufficient, try to find a smaller valid time (`right = mid - 1`).
   - If not, increase the time (`left = mid + 1`).
   - The final answer will be the smallest valid `mid`.

# Complexity
- **Time complexity:**  
  $$O(n \log (\max(\text{ranks}) \times \text{cars}^2))$$  
  - The binary search runs in `O(log (maxRank * cars^2))`.
  - For each binary search step, we iterate through `n` mechanics, making it `O(n log(...))`.

- **Space complexity:**  
  $$O(1)$$  
  - Only a few extra variables are used.

# Code
```cpp
class Solution {
public:
    bool isvalid(vector<int>& ranks, int cars, long long mid) {
        long long max_cars = 0;
        for (int x : ranks) {
            long long val = mid / (long long)x;
            max_cars += sqrt(val);
            if (max_cars >= cars) {
                return true;
            }
        }
        return (max_cars >= cars);
    }

    long long repairCars(vector<int>& ranks, int cars) {
        long long left = 1;
        long long n = (long long)cars * cars;
        long long maxrank = *max_element(ranks.begin(), ranks.end());
        long long right = maxrank * n;
        long long ans = 0;

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

['C++']