Easy C++ logic, Fully Explained with Intuition, thought process and *Common mistakes*
IntuitionI knew it was binary search week, but in an interview, you'd probably need a hint to use BS.
Think of ranges for the answer while you solve.ApproachI s
# Intuition
I knew it was binary search week, but in an interview, you'd probably need a hint to use BS.
Think of ranges for the answer while you solve.

# Approach
I started off by thinking of **binary search on the answer**, which is **time** in this case.

First, figure out the boundary, i.e., the smallest and largest possible times:
- **Smallest time:** `1 minute`
- **Largest time:** `max_element(rank) * cars * cars` (from the formula `r * n^2`)
  
So, we initialize:
- `low = 1 minute`
- `high = max_ele * cars * cars`

Now, applying **standard binary search on time**, we define another function `validTime`, which checks whether a given **assumedCorrectTime** is valid. It returns `true` if we can repair all cars within this time.

### Determining Valid Time
For each mechanic in the `ranks` array, we check:
- **Can they fix `totalCars` within `assumedCorrectTime`?**

To answer this, we need to determine:
- **The maximum number of cars each mechanic can fix within `assumedCorrectTime`**

### Finding Maximum Cars a Mechanic Can Fix
For this, we write another function `validCars` that returns the maximum cars each mechanic can fix in `assumedCorrectTime`.

In this function, the range for cars is:
- **Low:** `0` (minimum cars a mechanic can fix)
- **High:** `totalCars`

Again, we apply **binary search on the number of cars**:
- For each `mid` (possible number of cars repaired), we check the **repair time**.
- If `repairTime <= time`, store the answer and search for a higher value.
- Otherwise, search for a lower value.

Finally, `validCars` returns the **max cars each mechanic can fix** in `assumedCorrectTime`.

This value is received by `validTime`, which adds it to `carsRepaired`. As soon as `carsRepaired >= totalCars`, we return `true`.

This result is then passed back to the **main binary search function**, which updates `high = mid - 1` and continues searching for the minimum valid time.

---

### **Major mistake I was doing:**  
While calculating the **high boundary** for time in the main function:

long long high = cars * cars * max_ele;

this was giving me integer overflow for high. 

But long long has a range till 1e19, and cars*cars only goes till 1e12
so i was confused why its not working .

The problem was on RHS the cars and max_ele were integer so the system was treating it as int*int. 
To overcome this we have to change the type for cars

so correct is
ll h = (ll)cars * (ll)cars * *max_element(ranks.begin(), ranks.end());



# Complexity  
- **Time complexity:** $$O(M \cdot N \cdot \log M + N \cdot \log M)$$  
  - **Outer binary search on time:** $$O(\log M)$$  
  - **Checking validity (`validTime`) per iteration:** $$O(N)$$  
  - **Inner binary search on cars (`validCars`) per mechanic:** $$O(\log M)$$  
  - **Total mechanics (`N`) processing each iteration:** $$O(N \cdot \log M)$$  
  - **Final complexity:** $$O(M \cdot N \cdot \log M + N \cdot \log M)$$ (dominant term: $$O(M \cdot N \cdot \log M)$$)  

- **Space complexity:** $$O(1)$$ (only a few extra variables, no additional data structures)  



# Code
```cpp []class Solution {
public:
    typedef unsigned long long ll;

    // Binary search to find max cars a mechanic can fix within given time
    ll validCars(ll cars, ll rank, ll time) {
        ll l = 0, h = cars, carsRepaired = 0;
        while (l <= h) {
            ll m = l + (h - l) / 2;
            ll repairTime = rank * m * m;
            if (repairTime <= time) {
                carsRepaired = m;
                l = m + 1; // Search for more cars that can be repaired
            } else {
                h = m - 1;
            }
        }
        return carsRepaired;
    }

    // Checks if a given time is sufficient to repair all cars
    bool validTime(ll time, vector<int>& ranks, ll cars) {
        ll carsRepaired = 0;
        for (ll rank : ranks) {
            carsRepaired += validCars(cars, rank, time);
            if (carsRepaired >= cars) return true; // Early stopping
        }
        return false;
    }

    // Main function applying binary search on the minimum required time
    long long repairCars(vector<int>& ranks, int cars) {
        ll l = 1;
        ll h = (ll)cars * (ll)cars * *max_element(ranks.begin(), ranks.end());
        ll ans = h;

        while (l <= h) {
            ll m = l + (h - l) / 2;
            if (validTime(m, ranks, cars)) {
                h = m - 1; // Try for a smaller time
                ans = m;
            } else {
                l = m + 1; // Increase time if not enough cars are repaired
            }
        }
        return ans;
    }
};
```
['Array', 'Binary Search', 'C++']