Count freq & binary search of Koko's type||beats 100%
IntuitionAgain binary searching of Koko's type. A rank x mechanic can repair n cars in t=x * n^2 min. In other word, n=[xt​​]
But wait, look at the constraints
# Intuition
<!-- Describe your first thoughts on how to solve this problem. -->
Again binary searching of Koko's type. A rank x mechanic can repair n cars in `t=x * n^2` min. In other word, $n=[\sqrt{\frac{t}{x}}]$ 
But wait, look at the constraints 
> 1 <= ranks.length <= 10^5
1 <= ranks[i] <= 100
1 <= cars <= 10^6

There are many i's with the same values `rank[i]`. the computation for  `sqrt` is slow; so, count the `freq` for x in nums at first. **The 0ms code is achieved, but without counting `freq` it needs time more than 20ms!**
Python code is made with elapsed time 15m, even faster than some C++ implememation.
# Approach
<!-- Describe your approach to solving the problem. -->
1. Declare `freq[101], minR & maxR` as member variables where `minR, maxR` denote the min , max of `ranks`
2. Define the check function `bool canRepair(int cars, long long t)` to judge whether these `cars` can be repaired within time `t`; the loop is proceeded as follows
```
for(int x=minR; x<=maxR; x++) {
    cnt+=freq[x]*(long long)sqrt(t/x);//same x needs only once sqrt
    if (cnt>=cars) return 1; //more than cars can be repaired
}
return cnt>=cars;// last check
```
3. In `repairCars(vector<int>& ranks, int cars)` proceed the trasversal to find `freq[101], minR & maxR`

4. For shranking the search range, set `l=1, r=1LL*minR*cars*cars` 

5. It's to note during the loop `while(l<r){...}`, when `r=m, l=m+1` is used **the lower mid should be taken**

6. Very similar to solve [875. Koko Eating Bananas](https://leetcode.com/problems/koko-eating-bananas/solutions/3685871/w-explanation-easy-binary-search-c-solution/)
[Please turn on the English subtitles]
[https://youtu.be/KtZOZ4E1zww?si=o3rhF07qrvaTJn1z](https://youtu.be/KtZOZ4E1zww?si=o3rhF07qrvaTJn1z)
7. Python code is made; `Counter` is used for counting `freq` which is fast 
# Complexity
- Time complexity:
<!-- Add your time complexity here, e.g. $$O(n)$$ -->
$O(n+(M-m)\log(M\times cars^2))$ where `m, M=minR, maxR`
- Space complexity:
<!-- Add your space complexity here, e.g. $$O(n)$$ -->
$O(101)$
# Code||C++ 0ms beats 100%|Python 15ms Beats 98.15%
```cpp []
class Solution {
public:
    int freq[101]={0}, minR=101, maxR=0;
    inline bool canRepair(int cars, long long t){
        long long cnt=0;
        for(int x=minR; x<=maxR; x++) {
            cnt+=freq[x]*(long long)sqrt(t/x);
            if (cnt>=cars) return 1;
        }
        return cnt>=cars;
    }
    long long repairCars(vector<int>& ranks, int cars) {
        for(int x: ranks){
            minR=min(x, minR);
            maxR=max(x, maxR);
            freq[x]++;
        }
        long long l=1, r=1LL*minR*cars*cars, m;
        
        while(l<r){
            m=(l+r)/2;
            if (canRepair(cars, m)) r=m;
            else l=m+1;
        }
        return l; 
    }
};
```
```Python []
class Solution:
    def repairCars(self, ranks: List[int], cars: int) -> int:
        freq=Counter(ranks)
        minR=min(ranks)
    #    maxR=max(ranks) # no need
        def canRepair(t):
            cnt=0
            for x, f in freq.items():
                cnt+=f*(sqrt(t/x)//1)
                if cnt>=cars: return True
            return cnt>=cars
        
        l, r=1, minR*cars*cars
        while l<r:
            m=(l+r)>>1
            if canRepair(m):
                r=m
            else:
                l=m+1
        return l
        
```
['Binary Search', 'C++', 'Python3']