[Java/C++/Python] Binary Search and Heap Solution
Intuition\nBinary search the result.\n\n\n# Explanation\nBecause cars > 0,\nleft = 1.\n\nBecause mechanic A[i] can repair n cars in A[i] * n * nminutes.\nright 
# **Intuition**\nBinary search the result.\n<br>\n\n# **Explanation**\nBecause `cars > 0`,\n`left = 1`.\n\nBecause mechanic `A[i]` can repair `n` cars in `A[i] * n * n `minutes.\nright = `A[0] * cars * cars`.\n\nBinary search the time taken to repair all the cars.\nAssume we have `mid` minutes,\nthen the `i`th mechanic can repaire `sqrt(mid / A[i]` cars,\nand we round to floor integer here.\nWe calculate all the `cur` cars we can repair,\nIf `cur < cars`, not enough time, `left = mid + 1`\nIf `cur >= cars`, enough time, `right = mid`.\n\nFinally return the binary search result.\n<br>\n\n# **Complexity**\nIf count the frequency of all `A[i]`,\nsince `A[i] <= 100`,\nthen don\'t have to `O(n)` pass the whole `A` each time.\n\nTime `O(100 * (logA[0] + logcars))`,\nSpace `O(1)`\n<br>\n\n**Java**\n```java\n    public long repairCars(int[] A, int cars) {\n        long left = 1, right = 1L * A[0] * cars * cars;\n        while (left < right) {\n            long mid = (left + right) / 2, cur = 0;\n            for (int a : A)\n                cur += (long)(Math.sqrt(1.0 * mid / a));\n            if (cur < cars)\n                left = mid + 1;\n            else\n                right = mid;\n        }\n        return left;\n    }\n```\n\n**C++**\n```cpp\n    long long repairCars(vector<int>& A, int cars) {\n        long long left = 1, right = 1L * A[0] * cars * cars;\n        while (left < right) {\n            long long mid = (left + right) / 2, cur = 0;\n            for (int a : A)\n                cur += int(sqrt(1.0 * mid / a));\n            if (cur < cars)\n                left = mid + 1;\n            else\n                right = mid;\n        }\n        return left;\n    }\n```\n\n**Python**\n```py\n    def repairCars(self, A: List[int], cars: int) -> int:\n        count = Counter(A)\n        left, right = 1, min(count) * cars * cars\n        while left < right:\n            mid = (left + right) // 2\n            if sum(isqrt(mid // a) * count[a] for a in count) < cars:\n                left = mid + 1\n            else:\n                right = mid\n        return left\n```\n<br>\n\n\n# Solution 2: Heap\n\nAdd all worker in the a heap,\nand find out the next worker that can repair cars.\n\nTime `O(cars * log100)`,\nSpace `O(log100)`\n\n**Python**\n```py\n    def repairCars(self, A: List[int], cars: int) -> int:\n        count = Counter(A)\n        h = [[a, a, 1, count[a]] for a in count]\n        heapify(h)\n        while cars > 0:\n            time, rank, k, count = heappop(h)\n            cars -= count\n            k += 1\n            heappush(h, [rank * k * k, rank, k, count])\n        return time\n```\n<br>\n\n\n# More Good Binary Search Problems\nHere are some similar binary search problems.\nAlso find more explanations.\nGood luck and have fun.\n\n- 2560. [House Robber IV](https://leetcode.com/problems/house-robber-iv/discuss/3143697/JavaC%2B%2BPython-Binary-Search-O(1)-Space)\n- 2226. [Maximum Candies Allocated to K Children](https://leetcode.com/problems/maximum-candies-allocated-to-k-children/discuss/1908888/JavaC%2B%2BPython-Binary-Search-with-Explanation)\n- 1802. [Maximum Value at a Given Index in a Bounded Array](https://leetcode.com/problems/maximum-value-at-a-given-index-in-a-bounded-array/discuss/1119801/Python-Binary-Search)\n- 1539. [Kth Missing Positive Number](https://leetcode.com/problems/kth-missing-positive-number/discuss/779999/JavaC++Python-O(logN))\n- 1482. [Minimum Number of Days to Make m Bouquets](https://leetcode.com/problems/minimum-number-of-days-to-make-m-bouquets/discuss/686316/javacpython-binary-search)\n- 1283. [Find the Smallest Divisor Given a Threshold](https://leetcode.com/problems/find-the-smallest-divisor-given-a-threshold/discuss/446376/javacpython-bianry-search)\n- 1231. [Divide Chocolate](https://leetcode.com/problems/divide-chocolate/discuss/408503/Python-Binary-Search)\n- 1011. [Capacity To Ship Packages In N Days](https://leetcode.com/problems/capacity-to-ship-packages-within-d-days/discuss/256729/javacpython-binary-search/)\n- 875. [Koko Eating Bananas](https://leetcode.com/problems/koko-eating-bananas/discuss/152324/C++JavaPython-Binary-Search)\n- 774. [Minimize Max Distance to Gas Station](https://leetcode.com/problems/minimize-max-distance-to-gas-station/discuss/113633/Easy-and-Concise-Solution-using-Binary-Search-C++JavaPython)\n- 410. [Split Array Largest Sum](https://leetcode.com/problems/split-array-largest-sum/)\n<br>\n
['C', 'Python', 'Java']