✅Simple Solution In C With Explanation! | BINARY-SEARCH | BEATS 100% |
Intuition
The problem involves multiple mechanics (with different efficiency ranks) repairing a given number of cars as quickly as possible.
The time taken by a
# Intuition
- The problem involves multiple mechanics (with different efficiency ranks) repairing a given number of cars as quickly as possible.
- The time taken by a mechanic with rank `r` to fix `k` cars follows the formula: $$T = r \times k^2$$
- where `T` is the time required. Our goal is to minimize the maximum time taken to repair all cars.
- Since the time taken by each mechanic grows quadratically with the number of cars they repair, we can use **binary search** to efficiently find the minimum possible time required.
---
# Approach
1. **Binary Search on Time:**  
   - The minimum possible time (`left`) is `0`, and the maximum (`right`) is determined by the slowest mechanic working on all cars (`min(ranks) * cars^2`).
   - We perform a binary search to find the smallest `mid` such that the total number of cars repaired within `mid` time is at least `cars`.

2. **Checking Feasibility (numFixed function):**  
   - For a given `mid`, determine how many cars can be repaired.
   - Each mechanic can repair `floor(sqrt(mid / rank))` cars within `mid` time.
   - Sum up all these contributions and check if it meets or exceeds `cars`.

3. **Adjust Search Space:**  
   - If we can repair at least `cars` cars within `mid` time, move `right` to `mid` (try to minimize time).
   - Otherwise, increase `left` to `mid + 1`.
---
# Complexity
- ## **Time complexity:**  
  - Binary search runs in $$O(log (min(ranks) * cars^2))$$.
  - Each iteration computes the number of cars repaired in $$O(n)$$, where $$n$$ is $$ranksSize$$.
  - So the overall complexity is $$O(n log (cars^2))$$ or approximately $$O(n log cars)$$.

- ## **Space complexity:**  
  - We use only a few integer variables, so it's $$O(1)$$.
---
# Code
```c []
#include <math.h>
long long numFixed(int* ranks, int ranksSize, long long mid) {
    long long ans = 0;
    for (int i = 0; i < ranksSize; i++) {
        ans += sqrt(mid / ranks[i]);
    }
    return ans;
}
long long repairCars(int* ranks, int ranksSize, int cars) {
    long long left, right;
    left = 0;
    for (int i = 0; i < ranksSize; i++) {
        right = (ranks[i] < right) ? ranks[i] : right;
    }
    right = (long long) right * cars * cars;

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

    return left;
}
```
['Array', 'Math', 'Binary Search', 'Greedy', 'C', 'Simulation']