Binary search || C++ || obviously hard to think first
IntuitionThe idea is to minimize the time required to repair a given number of cars using mechanics of different ranks.
Each mechanic with rank r takes r * t^2

# Intuition  
The idea is to **minimize the time required** to repair a given number of cars using mechanics of different ranks.  
Each mechanic with rank `r` takes `r * t^2` time to repair `t` cars.  
So, in a given time `m`, a mechanic of rank `r` can repair at most `floor(sqrt(m / r))` cars.  
Thus, we binary search on the minimum time needed such that total cars repaired by all mechanics ≥ required cars.

---

# Approach  
- Perform **binary search** on time from `l = 1` to `r = max_rank * cars^2`.  
- In each iteration, check whether `m` (mid time) is sufficient to repair all cars using the `check()` function.
- In the `check()` function:
  - For each mechanic:  
    - `cars_by_this_mechanic = sqrt(m / rank[i])`
    - Add this to total count `no`.
    - If `no >= cars`, return `true` early (optimization).
- Update answer accordingly and shrink search space.

---

# Complexity
- **Time Complexity:**  
  $$O(n \cdot \log(\text{max(rank)} \cdot \text{cars}^2))$$  
  where `n` = number of mechanics (size of `ranks`).

- **Space Complexity:**  
  $$O(1)$$ (constant extra space)

---

# Example Walkthrough (Based on Your Code Execution)

Let's go through the **actual values as per your code**:

### Example:
```cpp
ranks = [4, 2, 3, 1];
cars = 10;
```

| Step | l | r | m (mid) | Cars Repaired (via check(m)) | Is m valid? (>=10 cars?) | Action |
|------|----|--------|---------|-----------------------------|--------------------------|--------|
| 1 | 1 | 400 | 200 | `floor(sqrt(200/4)) + sqrt(200/2) + sqrt(200/3) + sqrt(200/1)` = 7 + 10 + 8 + 14 = **39** | ✅ Yes | Try smaller time: r = m-1 |
| 2 | 1 | 199 | 100 | 5 + 7 + 5 + 10 = **27** | ✅ Yes | r = 99 |
| 3 | 1 | 99 | 50 | 3 + 5 + 4 + 7 = **19** | ✅ Yes | r = 49 |
| 4 | 1 | 49 | 25 | 2 + 3 + 2 + 5 = **12** | ✅ Yes | r = 24 |
| 5 | 1 | 24 | 12 | 1 + 2 + 2 + 3 = **8** | ❌ No | l = 13 |
| 6 | 13 | 24 | 18 | 2 + 3 + 2 + 4 = **11** | ✅ Yes | r = 17 |
| 7 | 13 | 17 | 15 | 1 + 2 + 2 + 3 = **8** | ❌ No | l = 16 |
| 8 | 16 | 17 | 16 | 2 + 2 + 2 + 4 = **10** | ✅ Yes | r = 15 |

✅ **Answer = 16 (Minimum time required)**

---



# Code
```cpp []
class Solution {
public:
    bool check(long long m,vector<int>& ranks, int cars){
        long long no=0;
        for(long long i=0;i<ranks.size();i++){
            long long c=sqrt((long long)m/(long long)ranks[i]);
            no+=c;
            if(no>=cars){
                return true;
            }
        }
        return false;
    }
    long long repairCars(vector<int>& ranks, int cars) {
        long long l=1;
        long long r= 1LL*(*max_element(ranks.begin(),ranks.end()))*cars*cars;
        long long ans=0;
        while(r>=l){
            long long m= l+(r-l)/2;
            if(check(m,ranks,cars)){
                ans=m;
                r=m-1;
            }
            else{
                l=m+1;
            }
        }
        return ans;
    }
};
```
['Binary Search', 'C++']