Today I have done leetcode's March LeetCoding Challenge with cpp.

March LeetCoding Challenge 16

Description

Minimum Time to Repair Cars

You are given an integer array ranks representing the ranks of some mechanics. ranks_i is the rank of the i^th mechanic. A mechanic with a rank r can repair n cars in r * n2 minutes.

You are also given an integer cars representing the total number of cars waiting in the garage to be repaired.

Return the minimum time taken to repair all the cars.

Note: All the mechanics can repair the cars simultaneously.

Example 1:

Input: ranks = [4,2,3,1], cars = 10
Output: 16
Explanation: 
- The first mechanic will repair two cars. The time required is 4 * 2 * 2 = 16 minutes.
- The second mechanic will repair two cars. The time required is 2 * 2 * 2 = 8 minutes.
- The third mechanic will repair two cars. The time required is 3 * 2 * 2 = 12 minutes.
- The fourth mechanic will repair four cars. The time required is 1 * 4 * 4 = 16 minutes.
It can be proved that the cars cannot be repaired in less than 16 minutes.​​​​​

Example 2:

Input: ranks = [5,1,8], cars = 6
Output: 16
Explanation: 
- The first mechanic will repair one car. The time required is 5 * 1 * 1 = 5 minutes.
- The second mechanic will repair four cars. The time required is 1 * 4 * 4 = 16 minutes.
- The third mechanic will repair one car. The time required is 8 * 1 * 1 = 8 minutes.
It can be proved that the cars cannot be repaired in less than 16 minutes.​​​​​

Constraints:

• 1 <= ranks.length <= 105
• 1 <= ranks[i] <= 100
• 1 <= cars <= 106

Solution

class Solution {
  bool validate(vector<int>& ranks, long long cars, long long time) {
    for(auto r : ranks) {
      long long repaired = sqrt(time / r);
      cars -= repaired;
    }
    return cars < 1;
  }
public:
  long long repairCars(vector<int>& ranks, int cars) {
    long long high = 1LL * *max_element(ranks.begin(), ranks.end()) * cars * cars;
    long long low = 1;
    while(low < high) {
      long long mid = (high + low) / 2;
      if(validate(ranks, cars, mid)) {
        high = mid;
      } else {
        low = mid + 1;
      }
    }
    return high;
  }
};

// Accepted
// 1072/1072 cases passed (43 ms)
// Your runtime beats 65.91 % of cpp submissions
// Your memory usage beats 45.76 % of cpp submissions (59.4 MB)