🔥Binary Search | Beginner Friendly | Java✅ | C++✅
Intuition
We have multiple mechanics, each with a repair rate given in the array arr. The time taken by a mechanic to repair x cars follows the formula:
time=𝑟×
# Intuition
<!-- Describe your first thoughts on how to solve this problem. -->
- We have multiple mechanics, each with a repair rate given in the array arr. The time taken by a mechanic to repair x cars follows the formula:
time=𝑟×𝑥^2 
where r is the mechanic's repair rate. Our goal is to find the minimum time required to repair exactly car number of cars.
We use binary search on time since it is the independent variable that affects the number of cars repaired.

# Approach
<!-- Describe your approach to solving the problem. -->
1. Binary Search on Time:

- The minimum possible time is 1, and the maximum can be a very large value (set as Long.MAX_VALUE initially).
- We perform binary search on this time range.

2. Check Feasibility (timetaken function):

- For a given time mid, check how many cars can be repaired.
- A mechanic with repair rate arr[i] can repair floor(sqrt(mid / arr[i])) cars in mid time.
- Sum up the number of cars all mechanics can repair.
- If we can repair at least car cars within mid time, we move towards a smaller time (r = mid - 1).
- Otherwise, we increase time (l = mid + 1).

3. Final Answer:

- The minimum feasible mid that allows car cars to be repaired is our answer.

# Complexity
Time complexity:
=
- Sorting the array: O(NlogN)
- Binary Search on Time: O(logT), where T is the upper bound on time.
- Checking feasibility (timetaken function): O(N) per binary search iteration.
- Since binary search runs in O(logT) and each feasibility check takes O(N), the total complexity is: O(NlogN+NlogT)≈O(NlogT) where T is the maximum possible time.
<!-- Add your time complexity here, e.g. $$O(n)$$ -->

Space complexity:
=
- Only a few extra variables are used (long variables, mid, ans, etc.)
- No extra data structures used → O(1) auxiliary space
<!-- Add your space complexity here, e.g. $$O(n)$$ -->

PLEASE UPVOTE⚠⚠⚠
=
# Code
```java []
class Solution {
    public long repairCars(int[] arr, int car) {
        long l=1,r=Long.MAX_VALUE,mid;
        long ans=Long.MAX_VALUE;
        Arrays.sort(arr);
        while(l<=r)
        {
            mid=l+(r-l)/2;
            long a=timetaken(arr,mid,car);
            if(a<ans)
            {
                ans=a;
                r=mid-1;
            }
            else
            l=mid+1;
        }
        return ans;
    }
    public long timetaken(int[] arr, long mid, int car)
    {
        int carscount=0;
        for(int i=0;i<arr.length;i++)
        {
            carscount+=Math.sqrt(mid/arr[i]);
            if(carscount>=car)
            return mid;
        }
        return Long.MAX_VALUE;
    }
}
```
# Code
```Cpp []
#include <bits/stdc++.h>
using namespace std;

class Solution {
public:
    long long repairCars(vector<int>& arr, int car) {
        sort(arr.begin(), arr.end());
        long long l = 1, r = LLONG_MAX, mid, ans = LLONG_MAX;

        while (l <= r) {
            mid = l + (r - l) / 2;
            if (timetaken(arr, mid, car)) {
                ans = mid;
                r = mid - 1;
            } else {
                l = mid + 1;
            }
        }
        return ans;
    }

private:
    bool timetaken(vector<int>& arr, long long mid, int car) {
        long long carscount = 0;
        for (int i = 0; i < arr.size(); i++) {
            carscount += sqrt(mid / arr[i]);
            if (carscount >= car) return true;
        }
        return false;
    }
};

```
['Array', 'Binary Search', 'C++', 'Java']