Binary Search
Time complexity is O(n log m), where m is maximum time.\n\nNote that we could argue that finding the square root is O(log m). However, processors implement sqrt
Time complexity is O(n log m), where m is maximum time.\n\nNote that we could argue that finding the square root is O(log m). However, processors implement `sqrt` efficiently so it takes O(1), so it would not be a big mistake if we ignore it.\n\n**Python 3**\nTIL: `isqrt`.\n\n```python\nclass Solution:\n    def repairCars(self, ranks: List[int], cars: int) -> int:\n        l, r = 1, 100 * 1000000 * 1000000  # rank * n * n\n        while l < r:\n            m = (l + r) // 2\n            rep = sum(isqrt(m // rank) for rank in ranks)\n            r = m if rep >= cars else r\n            l = m + 1 if rep < cars else l\n        return l\n```\n\n**C++**\n```cpp    \nlong long repairCars(vector<int>& ranks, int cars) {\n    long long l = 1, r = 100LL * 1000000 * 1000000; // rank * n * n\n    while (l < r) {\n        long long m = (l + r) / 2, rep = accumulate(begin(ranks), end(ranks), 0LL, \n            [m](long long sum, int rank){ return sum  + sqrt(m / rank); });\n        r = rep >= cars ? m : r;\n        l = rep >= cars ? l : m + 1;\n    }\n    return l;\n}\n```
['C']