Easy binary search | N log(n) | c++ | List of BS problems
Intuition\nIf we are asked for the minimum time to do something, it is possibly a binary search :)   \n\n# Approach\n\nFirst we define a classical binary search
# Intuition\nIf we are asked for the minimum time to do something, it is possibly a binary search :)   \n\n# Approach\n\nFirst we define a classical binary search for the problem, we define the function $check$ that tells the number of cars that all workers can repair in $T$ time, it is clear that we just need to get this sum: $TotalCarsRepaired = \\Sigma \\frac{T}{t_i}$ and as that means the number of cars that the whole team can repair we just need to compare with $cars$ to know if that time is valid, i.e. $TotalCarsRepaired \\geq cars$.\n\nThis is a classic binary search problem, but in our problem the time $t_i$  that some worker uses to repair $1$ car is not given, but the problem gives a total time depending on the number of cars, which forces to change a little the summation. \n\nNow instead of obtaining $t_i$ for each worker we obtain $n_i$ (maximum number of cars that worker $i$ can repair in $T$ time). For each worker $i$,the problem states that. \n$t_i$ depends on the number of cars he repaired. $r_i \\times n_i^2$ so here we have the value $n_i$ we are looking for, let\'s define the inequation $r_i \\times n_i^2 \\leq T$ which must be true for some $T$. \n\nTherefore, we can manipulate the equation to obtain the maximum possible $n_i$ \n$$ r_i \\times n_i^2 \\leq T$$\n$$ n_i^2 \\leq \\frac{T}{r_i} $$\n$$ n_i^2 \\sqrt \\frac{T}{r_i} $$\n\nSo for each worker we can know the maximum number of cars that can be repaired by them, now the summation is $TotalCarsRepaired = \\Sigma n_i$ now we can use this function to properly move our binary search.\n\n# More problems \nA list of similar problems including the easy version of this.\n[Medium - the easy version](https://leetcode.com/problems/minimum-time-to-complete-trips/)\n[Medium - similar](https://leetcode.com/problems/koko-eating-bananas/)\n[Medium - similar](https://leetcode.com/problems/capacity-to-ship-packages-within-d-days/)\n[Hard - similar](https://leetcode.com/problems/maximum-running-time-of-n-computers/)\n[Medium](https://leetcode.com/problems/find-minimum-in-rotated-sorted-array/description/)\n[Hard](https://leetcode.com/problems/find-k-th-smallest-pair-distance/description/)\n\n# Complexity\n- Time complexity:\n$O(n log(n))$\n\n# Code\n```\nclass Solution {\npublic:\n    bool check(vector<int> &v,int N,long long t){\n        long long pos = 0;\n        for(int i = 0;i<v.size();i++){\n            long long n = sqrt(t/v[i]);\n            pos+=n;\n            if(pos>=N)return true;\n        }\n        if(pos>=N)return true;\n        return false;\n    }\n    \n    long long repairCars(vector<int>& ranks, int cars) {\n        long long l = 0,r = 1e16;\n        while(l+1<r){\n            long long m = (l+r)>>1;\n            if(check(ranks,cars,m))r = m;\n            else l = m;\n        }\n        return r;\n    }\n};\n```
['C++']