# 2594. Minimum Time to Repair Cars

• Time: $O(\log (\min(\texttt{ranks}) \cdot \texttt{cars}^2))$
• Space: $O(1)$
  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 class Solution { public: long long repairCars(vector& ranks, int cars) { long long l = 0; long long r = 1LL * *min_element(ranks.begin(), ranks.end()) * cars * cars; while (l < r) { const long long m = (l + r) / 2; if (numCarsFixed(ranks, m) >= cars) r = m; else l = m + 1; } return l; } private: long long numCarsFixed(const vector& ranks, long long minutes) { long long carsFixed = 0; // r * n^2 = minutes // -> n = sqrt(minutes / r) for (const int rank : ranks) carsFixed += sqrt(minutes / rank); return carsFixed; } }; 
  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 class Solution { public long repairCars(int[] ranks, int cars) { long l = 0; long r = (long) Arrays.stream(ranks).min().getAsInt() * cars * cars; while (l < r) { final long m = (l + r) / 2; if (numCarsFixed(ranks, m) >= cars) r = m; else l = m + 1; } return l; } private long numCarsFixed(int[] ranks, long minutes) { long carsFixed = 0; // r * n^2 = minutes // -> n = sqrt(minutes / r) for (final int rank : ranks) carsFixed += Math.sqrt(minutes / rank); return carsFixed; } } 
  1 2 3 4 5 6 7 8 9 10 class Solution: def repairCars(self, ranks: List[int], cars: int) -> int: def numCarsFixed(minutes: int) -> int: # r * n^2 = minutes # -> n = sqrt(minutes / r) return sum(int(sqrt(minutes // rank)) for rank in ranks) return bisect.bisect_left( range(0, min(ranks) * cars**2), cars, key=lambda m: numCarsFixed(m))