Minimum time to repair cars Solution In C++/Python/Java
Minimum Time to Repair Cars Problem Description:
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 * n² 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.
Examples :
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.
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 <= 10⁵
1 <= ranks[i] <= 100
1 <= cars <= 10⁶
Brute Force Approach
To approach the problem, we need to determine the minimum time required to repair all the given cars using the available mechanics. Each mechanic has a rank, and the time they take to repair a given number of cars depends on this rank. The goal is to distribute the workload optimally among mechanics while minimizing the maximum time taken.
What Can Be the Minimum Possible Time?
The minimum time required should be 1, since even the fastest mechanic would need at least 1 minute to repair a car.
Now that we know the minimum possible time, what would be the Maximum Possible Time?
The maximum possible time required to repair all cars is given by max(ranks) × cars². This represents the worst-case scenario, where the slowest mechanic (the one with the maximum rank) is solely responsible for repairing all the cars. Since a mechanic with rank r takes r × n² time to repair n cars, the time taken by the slowest mechanic to repair all cars would be max(ranks) × cars².
Thus, our search space for the answer ranges from 1 to the maximum time required by the slowest mechanic to repair all cars (max(ranks) * cars * cars). Now, the problem reduces to finding the minimum possible time in which all cars can be repaired while distributing the workload among mechanics efficiently.
A basic approach is to iterate through all possible values from 1 to the maximum time required by the slowest mechanic and check whether it is possible to repair all cars within a given time limit. If it is possible, then it is a valid solution.
We continue this process until we find the minimum time that allows all cars to be repaired. We can either start from 1 and go up to the maximum possible time or start from the maximum possible time and go down to 1. The idea is to start from 1 to the maximum possible time and stop whenever we find the point where it's not possible to repair all cars within that time, then return the previous point as it was the minimum valid time required.
Consider ranks = [4, 2, 3, 1] and cars = 10. We start by setting the smallest possible time as 1 and the largest possible time as the time required by the slowest mechanic to repair all cars.
We then check how many cars can be repaired within different values of time:
- If the time is 1, only a few cars can be repaired, so it does not work.
- If the time is 5, some mechanics can repair more cars, but it is still insufficient.
- If the time is 10, more mechanics contribute, but not all cars are repaired.
- If the time is 16, all 10 cars can be repaired efficiently by distributing the workload among mechanics.
- If the time is 17 or more, all 10 cars can be repaired efficiently by distributing the workload among mechanics.
Since 16 is the smallest time in which all cars can be repaired, it is the answer.
We can see that any time less than 16 does not allow all cars to be repaired, but as soon as we reach 16, the repair is possible.
Let's call the minimum possible time required to repair all cars as minTime. Any number less than minTime won’t work because it will always result in fewer than the required number of cars being repaired within that time. However, any number greater than or equal to minTime will allow us to complete the repairs.
Therefore, minTime is the smallest possible time in which all cars can be repaired while distributing the workload efficiently among mechanics. Any value less than minTime won’t be sufficient, but as soon as we reach minTime, the repairs can be completed within the given constraints.
Explaining the Car Repair Allocation Process in Real-World Terms
Imagine you own a car repair shop where multiple mechanics with different skill levels (ranks) are available. Given a fixed time, you need to determine how many cars can be repaired within this time while ensuring each mechanic is utilized optimally.
Each mechanic follows a specific repair pattern based on their rank r:
A mechanic with rank r takes r × n² minutes to repair n cars. This means the time required to fix n cars by a single mechanic is:
Time = r × n²
Rearranging for n, we get:
n = sqrt(Time / r)
This formula helps determine how many cars a mechanic of rank r can repair within the given time.
To check if a solution is valid, we sum up the number of cars repaired by all mechanics in the fixed time. If the total is greater than or equal to the required number of cars, then the solution is valid.
Let's understand with an example:
Minimum Time to Repair Cars Example:
Input: ranks = [5,1,8], cars = 6
Step 1: Define Search Space
- Smallest possible time = 1
- Largest possible time = 8 × 6² = 288 (if the slowest mechanic repaired all cars alone)
- We iterate from 1 → 288 to find the minimum valid time.
Step 2: Checking Feasibility for Different Time Values
Time = 1
- Mechanic (Rank 5): √(1/5) = 0 (floor value)
- Mechanic (Rank 1): √(1/1) = 1
- Mechanic (Rank 8): √(1/8) = 0
Total cars repaired = 1 (Not enough)
Time = 10
- Rank 5: √(10/5) = 1
- Rank 1: √(10/1) = 3
- Rank 8: √(10/8) = 1
Total cars repaired = 5 (Not enough)
Time = 16
- Rank 5: √(16/5) = 1
- Rank 1: √(16/1) = 4
- Rank 8: √(16/8) = 1
Total cars repaired = 6 (Valid)
Step 3: Find Minimum Time
- time = 16 works, so we stop at 16 as it's the smallest valid time.
Final Answer: 16
Thus, the minimum time required to repair all 6 cars is 16 minutes.
Steps to Implement the Solution:
Define the Search Space
- The minimum possible time is 1, as at least 1 unit of time is required for repairs.
- The maximum possible time is calculated as:
(Maximum Rank) × (Total Cars)²
This represents the scenario where the fastest mechanic repairs all cars alone.
2. Implement a Function to Check Feasibility (isPossible)
- This function verifies if all cars can be repaired within a given time.
- Key Steps:
Initialize carsRepaired = 0.
Iterate through each mechanic’s rank:
Compute the number of cars the mechanic can repair using the formula:
carsRepaired += sqrt(time / rank)
This equation derives from the sum of an arithmetic series, as each mechanic requires increasing time per car.
If total repaired cars meet or exceed the required number, return true.
3. Perform a Linear Search for the Minimum Valid Time
- Iterate from low = 1 to high = max possible time.
- Use isPossible(ranks, cars, i) to check feasibility.
- If valid, update minTime and return the first feasible time.
Minimum Time to Repair Cars leetcode solution
Minimum Time to Repair Cars / Code Implementation
1. Minimum Time to Repair Cars solution in c++ Try on Compiler
class Solution {
// Function to check if it is possible to repair 'cars' within 'time' limit
bool isPossible(vector<int> &ranks, int cars, long long time)
{
// Initialize total repaired cars count
long long carsRepaired = 0;
// Iterate through each mechanic's rank
for(auto &rank : ranks)
{
// Calculate the number of cars this mechanic can repair in 'time' using the formula
carsRepaired += sqrt(time / rank);
}
// If total repaired cars are at least the required number of cars, return true
return carsRepaired >= cars;
}
public:
// Function to find the minimum time required to repair all cars
long long repairCars(vector<int>& ranks, int cars)
{
// Set the lower bound of the search space
long long low = 1;
// Set the upper bound as the slowest mechanic working alone on all cars
long long high = 1LL * (*max_element(ranks.begin(), ranks.end())) * cars * cars;
// Variable to store the minimum required time
long long minTime = 0;
// Perform a linear search from low to high to find the minimum valid time
for(int i = low; i <= high; i++)
{
// If 'i' is a valid time where all cars can be repaired, store it and break
if(isPossible(ranks, cars, i))
{
minTime = i;
break;
}
}
// Return the minimum time found
return minTime;
}
};
2. Minimum Time to Repair Cars solution in Java Try on Compiler
import java.util.*;
class Solution {
// Function to check if it is possible to repair 'cars' within 'time' limit
private boolean isPossible(int[] ranks, int cars, long time)
{
// Initialize total repaired cars count
long carsRepaired = 0;
// Iterate through each mechanic's rank
for (int rank : ranks)
{
// Calculate the number of cars this mechanic can repair in 'time' using the formula
carsRepaired += Math.sqrt(time / rank);
}
// If total repaired cars are at least the required number of cars, return true
return carsRepaired >= cars;
}
// Function to find the minimum time required to repair all cars
public long repairCars(int[] ranks, int cars)
{
// Set the lower bound of the search space
long low = 1;
// Set the upper bound as the slowest mechanic working alone on all cars
long high = (long) Arrays.stream(ranks).max().getAsInt() * cars * cars;
// Variable to store the minimum required time
long minTime = 0;
// Perform a linear search from low to high to find the minimum valid time
for (long i = low; i <= high; i++)
{
// If 'i' is a valid time where all cars can be repaired, store it and break
if (isPossible(ranks, cars, i))
{
minTime = i;
break;
}
}
// Return the minimum time found
return minTime;
}
}
3. Minimum Time to Repair Cars solution in Python Try on Compiler
import math
class Solution:
# Function to check if it is possible to repair 'cars' within 'time' limit
def isPossible(self, ranks, cars, time):
# Initialize total repaired cars count
carsRepaired = 0
# Iterate through each mechanic's rank
for rank in ranks:
# Calculate the number of cars this mechanic can repair in 'time' using the formula
carsRepaired += math.floor(sqrt(time / rank))
# If total repaired cars are at least the required number of cars, return True
return carsRepaired >= cars
# Function to find the minimum time required to repair all cars
def repairCars(self, ranks, cars):
# Set the lower bound of the search space
low = 1
# Set the upper bound as the slowest mechanic working alone on all cars
high = max(ranks) * cars * cars
# Variable to store the minimum required time
minTime = 0
# Perform a linear search from low to high to find the minimum valid time
for i in range(low, high + 1):
# If 'i' is a valid time where all cars can be repaired, store it and break
if self.isPossible(ranks, cars, i):
minTime = i
break
# Return the minimum time found
return minTime
4. Minimum Time to Repair Cars solution in Javascript Try on Compiler
/**
* @param {number[]} ranks
* @param {number} cars
* @return {number}
*/
// Function to check if it is possible to repair 'cars' within 'time' limit
var isPossible = function (ranks, cars, time) {
// Initialize total repaired cars count
let carsRepaired = 0;
// Iterate through each mechanic's rank
for (let rank of ranks) {
// Calculate the number of cars this mechanic can repair in 'time' using the formula
carsRepaired += Math.floor(Math.sqrt(time / rank));
}
// If total repaired cars are at least the required number of cars, return true
return carsRepaired >= cars;
}
var repairCars = function (ranks, cars) {
// Set the lower bound of the search space
let low = 1;
// Set the upper bound as the slowest mechanic working alone on all cars
let high = Math.max(...ranks) * cars * cars;
// Variable to store the minimum required time
let minTime = 0;
// Perform a linear search from low to high to find the minimum valid time
for (let i = low; i <= high; i++) {
// If 'i' is a valid time where all cars can be repaired, store it and break
if (isPossible(ranks, cars, i)) {
minTime = i;
break;
}
}
// Return the minimum time found
return minTime;
};Complexity Analysis of Minimum Time to Repair Cars (brute force):
Time Complexity: O((max(rank) × cars²) × n)
The given approach follows a linear search method to determine the minimum time required to repair all cars. Let's analyze the time complexity step by step.
1. Complexity of the isPossible Function
- The function iterates over the ranks array once.
- For each mechanic, it performs a square root operation, which is O(1).
- If there are n mechanics, the function runs in O(n) time.
2. Complexity of the repairCars Function
- The function searches for the minimum possible time using linear search.
- The search range is from 1 to high, where:
high = (maximum rank) × (cars²) - In the worst case, we iterate through every value in this range, leading to O(high) complexity.
- For each value in this range, we call isPossible(), which runs in O(n).
Thus, the overall time complexity is:
O(high × n) = O((max(rank) × cars²) × n)
This is highly inefficient for large values of cars, making the linear search approach suboptimal.
Space Complexity: O(n)
- Auxiliary Space Complexity: O(1)
The solution only uses a few integer and long long variables (minTime, low, high, carsRepaired, time), which take O(1) space.
Therefore, the auxiliary space complexity is O(1). - Total Space Complexity: O(n)
The ranks[] array takes O(n) space as input.
Therefore, the total space complexity is O(n).
Will Brute Force Work Against the Given Constraints?
For the current solution, the time complexity is O((max(rank) × cars²) × n), where n is the number of mechanics (with an upper limit of 10⁵), and max(rank) × cars² represents the worst-case time range (with an upper limit of 10⁸).
In the worst-case scenario, max(rank) × cars² could be as large as 10⁸, leading to a time complexity of O((max(rank) × cars²) × n).
This time complexity can become inefficient when max(rank) × cars² is large, particularly when cars is close to its upper bound (10⁶) and n is large (up to 10⁵). In such cases, the algorithm may perform a large number of operations (nearly 10¹³) and become impractical for large inputs.
This solution may not execute efficiently for all test cases, particularly when max(rank) × cars² is near its upper limit. While it may work for inputs with smaller values of cars or max(rank), it could exceed the time limits for large inputs where max(rank) × cars² is close to its maximum constraint.
In competitive programming environments, the typical time complexity limit is around 10⁶ operations per test case. Therefore, for inputs with large values of cars, this time complexity could lead to inefficient execution.
How to optimize it?
In the previous approach, we checked every possible value of time (from 1 to max(rank) × cars²) and verified if it was possible to repair cars within that time limit. This resulted in O((max(rank) × cars²) × n) time complexity, which was too slow and caused TLE (Time Limit Exceeded).
Now, let’s think about improving this.
The main issue was that we checked every possible value of time, which took too much time.
Can we make this part faster?
Yes! Here’s the hint:
We are searching for the minimum time required to repair all cars. We know this minimum time lies between 1 (minimum possible time) and max(rank) × cars² (maximum possible time).
Now that we know the two endpoints, 1 and min(rank) × cars², let's make a few observations:
- The data structure is sorted:
The range of possible values for time is naturally sorted from 1 to max(ranks) × cars². - The search space is monotonic:
- If a certain time allows us to repair all cars, then any larger time will also work.
- If a certain time does not allow us to repair all cars, then any smaller time will also fail.
- For example, consider ranks = [4,2,3,1] and cars = 10.
If we try time = 5, it definitely fails.
If we try time = 10, it may not be enough.
If we try time = 16, all cars can be repaired.
This demonstrates the monotonic property of the problem.
- The middle element helps minimize or maximize the search space:
If we take the middle value of the current range and check if it works (i.e., can we repair all cars within that time), we can narrow the search space:
- If it works, we move to the left half to find a smaller valid time.
- If it doesn’t work, we move to the right half to find a larger valid time.
If we plot a graph with the range of possible repair times on the x-axis and the number of cars that can be repaired at that time on the y-axis, we observe the following:
- For a given time, we can either successfully repair cars or fail to do so.
- Before reaching the minimum valid time (minTime), we cannot repair all cars.
- Once we reach minTime, repairing all cars remains feasible for any number greater than or equal to minTime.
This showcases the monotonic nature of the problem.
Thus, minTime represents the smallest possible time required to repair all cars. Once this number is found, repairing all cars remains feasible for any number greater than or equal to minTime.
With these points in mind, it's clear that instead of linearly checking all possible times from 1 to max(rank) × cars², we can take the middle value and continually reduce the search space.Does this approach remind you of something you've seen before?
Yes, we are applying binary search here. By leveraging the monotonic property of the possible repair times, we efficiently narrow down the search space to find the minimum time required to repair all cars, instead of checking each value linearly.
Minimum Time to Repair Cars Binary Search Algorithm
Binary search can help us quickly find the minimum time required to repair all cars while ensuring all cars are repaired within that time.
We can simply use binary search to determine the minimum time possible.
- Start by taking the middle value between low (1) and high (max(rank) × cars²).
- If this mid value satisfies the condition that we can repair all cars within mid time, we store it as a potential answer and narrow the search space to the left half, looking for a smaller valid value.
- Otherwise, we move the search to the right half to find a larger valid value.
- We continue this process as long as low ≤ high.
- Once the condition breaks, the stored answer is returned as the minimum possible time required to repair all cars.
By using binary search, we can cut the search space in half at each step, making the solution much faster and avoiding TLE issues.
Let us understand this with a video,
minimum-time-to-repair-cars-optimal-approach-animation
Let's understand with an example:
Minimum Time to Repair Cars Example:
Input: ranks = [5,1,8], cars = 6
Step 1: Define Search Space
- low = 1 (minimum possible time)
- high = max(ranks) × cars² = 8 × 6² = 288
Step 2: Apply Binary Search
Iteration 1:
Mid = (1 + 288) / 2 = 144
Check if time = 144 allows repairing 6 cars:
- Mechanic with rank 5 repairs √(144/5) ≈ 5 cars
- Mechanic with rank 1 repairs √(144/1) = 12 cars
- Mechanic with rank 8 repairs √(144/8) ≈ 4 cars
- Total cars repaired = 5 + 12 + 4 = 21 (Valid ✅)
- Store 144 as a potential answer and search for a smaller value (high = 143).
Iteration 2:
- Mid = (1 + 143) / 2 = 72
- Check if time = 72 allows repairing 6 cars:
- Mechanic with rank 5 repairs √(72/5) ≈ 3 cars
- Mechanic with rank 1 repairs √(72/1) = 8 cars
- Mechanic with rank 8 repairs √(72/8) ≈ 3 cars
- Total cars repaired = 3 + 8 + 3 = 14 (Valid ✅)
- Store 72 as a potential answer and search for a smaller value (high = 71).
Iteration 3:
- Mid = (1 + 71) / 2 = 36
- Check if time = 36 allows repairing 6 cars:
- Mechanic with rank 5 repairs √(36/5) ≈ 2 cars
- Mechanic with rank 1 repairs √(36/1) = 6 cars
- Mechanic with rank 8 repairs √(36/8) ≈ 2 cars
- Total cars repaired = 2 + 6 + 2 = 10 (Valid ✅)
- Store 36 as a potential answer and search for a smaller value (high = 35).
Iteration 4:
- Mid = (1 + 35) / 2 = 18
- Check if time = 18 allows repairing 6 cars:
- Mechanic with rank 5 repairs √(18/5) ≈ 1 car
- Mechanic with rank 1 repairs √(18/1) = 4 cars
- Mechanic with rank 8 repairs √(18/8) ≈ 1 car
- Total cars repaired = 1 + 4 + 1 = 6 (Valid ✅)
- Store 18 as a potential answer and search for a smaller value (high = 17).
Iteration 5:
- Mid = (1 + 17) / 2 = 9
- Check if time = 9 allows repairing 6 cars:
- Mechanic with rank 5 repairs √(9/5) ≈ 1 car
- Mechanic with rank 1 repairs √(9/1) = 3 cars
- Mechanic with rank 8 repairs √(9/8) ≈ 1 car
- Total cars repaired = 1 + 3 + 1 = 5 (Not enough ❌)
- Increase time (low = 10).
Iteration 6:
- Mid = (10 + 17) / 2 = 13
- Check if time = 13 allows repairing 6 cars:
- Mechanic with rank 5 repairs √(13/5) ≈ 1 car
- Mechanic with rank 1 repairs √(13/1) = 3 cars
- Mechanic with rank 8 repairs √(13/8) ≈ 1 car
- Total cars repaired = 1 + 3 + 1 = 5 (Not enough ❌)
- Increase time (low = 14).
Iteration 7:
- Mid = (14 + 17) / 2 = 15
- Check if time = 15 allows repairing 6 cars:
- Mechanic with rank 5 repairs √(15/5) ≈ 1 car
- Mechanic with rank 1 repairs √(15/1) = 3 cars
- Mechanic with rank 8 repairs √(15/8) ≈ 1 car
- Total cars repaired = 1 + 3 + 1 = 5 (Not enough ❌)
- Increase time (low = 16).
Iteration 8:
- Mid = (16 + 17) / 2 = 16
- Check if time = 16 allows repairing 6 cars:
- Mechanic with rank 5 repairs √(16/5) ≈ 1 car
- Mechanic with rank 1 repairs √(16/1) = 4 cars
- Mechanic with rank 8 repairs √(16/8) ≈ 1 car
- Total cars repaired = 1 + 4 + 1 = 6 (Valid ✅)
- Store 16 as a potential answer and search for a smaller value (high = 15).
Step 3: Termination
- Since low > high (16 > 15), binary search terminates.
- The minimum time required to repair all 6 cars is 16.
Final Output: 16 ✅
How to code it up:
Step 1: Define the Helper Function (isPossible)
- Initialize carsRepaired = 0 to count the number of cars repaired within the given time.
- Iterate through each mechanic's rank:
- Use the formula sqrt(time / rank) to calculate how many cars a mechanic can repair in the given time.
- Return true if the total repaired cars are at least the required number of cars, otherwise return false.
Step 2: Define the Main Function (repairCars)
- Get the number of mechanics from the ranks array.
- Define the search space:
- low = 1 → The smallest possible time.
- high = (max(ranks) * cars²) → The upper bound based on the slowest mechanic repairing all cars alone.
- minTime = 0 → Variable to store the minimum required time.
- Apply Binary Search:
- While low ≤ high:
- Compute mid = (low + high) / 2 as the candidate minimum time.
- Call isPossible(ranks, cars, mid):
- If true, update minTime = mid and search for a smaller time (high = mid - 1).
- If false, search for a larger time (low = mid + 1).
- Return minTime, which represents the minimum time required to repair all cars.
Minimum Time to Repair Cars Leetcode Solution
Minimum Time to Repair Cars solution / Code Implementation
1. Minimum Time to Repair Cars solution in c++ Try on Compiler
class Solution {
// Function to check if it is possible to repair 'cars' within 'time' limit
bool isPossible(vector<int> &ranks, int cars, long long time)
{
// Initialize total repaired cars count
long long carsRepaired = 0;
// Iterate through each mechanic's rank
for(auto &rank : ranks)
{
// Calculate the number of cars this mechanic can repair in 'time' using the formula
carsRepaired += sqrt(time / rank);
}
// If total repaired cars are at least the required number of cars, return true
return carsRepaired >= cars;
}
public:
// Function to find the minimum time required to repair all cars
long long repairCars(vector<int>& ranks, int cars)
{
// Set the lower bound of the search space
long long low = 1;
// Set the upper bound as the slowest mechanic working alone on all cars
long long high = 1LL * (*max_element(ranks.begin(), ranks.end())) * cars * cars;
// Variable to store the minimum required time
long long minTime = 0;
// Perform binary search to find the optimal minimum time
while(low <= high)
{
// Calculate the mid value (potential minimum time)
long long mid = (low + high) / 2;
// Check if it's possible to repair all cars within 'mid' time
if(isPossible(ranks, cars, mid))
{
// If possible, update the minimum time
minTime = mid;
// Try to find a smaller valid time
high = mid - 1;
}
else
{
// If not possible, search in the higher time range
low = mid + 1;
}
}
// Return the minimum time found
return minTime;
}
};
2. Minimum Time to Repair Cars solution in Java Try on Compiler
import java.util.*;
class Solution {
// Function to check if it is possible to repair 'cars' within 'time' limit
private boolean isPossible(int[] ranks, int cars, long time) {
// Initialize total repaired cars count
long carsRepaired = 0;
// Iterate through each mechanic's rank
for (int rank : ranks) {
// Calculate the number of cars this mechanic can repair in 'time' using the formula
carsRepaired += Math.sqrt(time / rank);
}
// If total repaired cars are at least the required number of cars, return true
return carsRepaired >= cars;
}
// Function to find the minimum time required to repair all cars
public long repairCars(int[] ranks, int cars) {
// Set the lower bound of the search space
long low = 1;
// Set the upper bound as the slowest mechanic working alone on all cars
long high = (long) Arrays.stream(ranks).max().getAsInt() * cars * cars;
// Variable to store the minimum required time
long minTime = 0;
// Perform binary search to find the optimal minimum time
while (low <= high) {
// Calculate the mid value (potential minimum time)
long mid = (low + high) / 2;
// Check if it's possible to repair all cars within 'mid' time
if (isPossible(ranks, cars, mid)) {
// If possible, update the minimum time
minTime = mid;
// Try to find a smaller valid time
high = mid - 1;
} else {
// If not possible, search in the higher time range
low = mid + 1;
}
}
// Return the minimum time found
return minTime;
}
}
3. Minimum Time to Repair Cars solution in Python Try on Compiler
import math
class Solution:
# Function to check if it is possible to repair 'cars' within 'time' limit
def isPossible(self, ranks, cars, time):
# Initialize total repaired cars count
carsRepaired = 0
# Iterate through each mechanic's rank
for rank in ranks:
# Calculate the number of cars this mechanic can repair in 'time' using the formula
carsRepaired += math.floor(sqrt(time // rank))
# If total repaired cars are at least the required number of cars, return True
return carsRepaired >= cars
# Function to find the minimum time required to repair all cars
def repairCars(self, ranks, cars):
# Set the lower bound of the search space
low = 1
# Set the upper bound as the slowest mechanic working alone on all cars
high = max(ranks) * cars * cars
# Variable to store the minimum required time
minTime = 0
# Perform binary search to find the optimal minimum time
while low <= high:
# Calculate the mid value (potential minimum time)
mid = (low + high) // 2
# Check if it's possible to repair all cars within 'mid' time
if self.isPossible(ranks, cars, mid):
# If possible, update the minimum time
minTime = mid
# Try to find a smaller valid time
high = mid - 1
else:
# If not possible, search in the higher time range
low = mid + 1
# Return the minimum time found
return minTime
4. Minimum Time to Repair Cars solution in Javascript Try on Compiler
/**
* @param {number[]} ranks
* @param {number} cars
* @return {number}
*/
// Function to check if it is possible to repair 'cars' within 'time' limit
var isPossible = function (ranks, cars, time) {
// Initialize total repaired cars count
let carsRepaired = 0;
// Iterate through each mechanic's rank
for (let rank of ranks) {
// Calculate the number of cars this mechanic can repair in 'time' using the formula
carsRepaired += Math.floor(Math.sqrt(time / rank));
}
// If total repaired cars are at least the required number of cars, return true
return carsRepaired >= cars;
}
var repairCars = function (ranks, cars) {
// Set the lower bound of the search space
let low = 1;
// Set the upper bound as the slowest mechanic working alone on all cars
let high = Math.max(...ranks) * cars * cars;
// Variable to store the minimum required time
let minTime = 0;
// Perform binary search to find the optimal minimum time
while (low <= high) {
// Calculate the mid value (potential minimum time)
let mid = Math.floor((low + high) / 2);
// Check if it's possible to repair all cars within 'mid' time
if (isPossible(ranks, cars, mid)) {
// If possible, update the minimum time
minTime = mid;
// Try to find a smaller valid time
high = mid - 1;
} else {
// If not possible, search in the higher time range
low = mid + 1;
}
}
// Return the minimum time found
return minTime;
};Complexity Analysis of Minimum Time to Repair Cars (binary search):
Time Complexity : O(n * log(max(ranks) × cars²))
The binary search approach significantly improves efficiency compared to a linear search. Let's analyze its time complexity step by step:
1. Binary Search Complexity
- We are performing binary search on the possible time range, which spans from 1 to (max(ranks) × cars²).
- The worst-case scenario occurs when max(ranks) = 1 and cars = 10⁶, leading to an upper bound of 10¹².
- The number of iterations in binary search is O(log (max(ranks) × cars²)).
- Since max(ranks) ≤ 100, the upper bound is approximately O(log (10² × 10¹²)) = O(log 10¹⁴) ≈ O(46), which is highly efficient.
2. Checking Feasibility (isPossible function)
- For each mid value in binary search, we iterate through all n mechanics in the ranks array.
- For each mechanic, we compute sqrt(time / rank), which takes O(1) time.
- The isPossible function runs in O(n) time.
Final Time Complexity
Since binary search takes O(log (max(ranks) × cars²)) iterations, and isPossible runs in O(n) for each iteration, the overall time complexity is: O(n * log(max(ranks) × cars²))
Given the constraints:
- n ≤ 10⁵
- cars ≤ 10⁶
- max(ranks) ≤ 100
This results in at most O(10⁵ × 46) ≈ O(4.6 × 10⁶) operations, which is efficient for large inputs.
Thus, this approach runs efficiently within competitive programming constraints (typically allowing ~10⁶ operations per second).
Space Complexity : O(n)
- Auxiliary Space Complexity: O(1)
The solution only uses a few integer and long long variables (minTime, low, high, carsRepaired, time), which take O(1) space.
Therefore, the auxiliary space complexity is O(1). - Total Space Complexity: O(n)
The ranks[] array takes O(n) space as input.
Therefore, the total space complexity is O(n).
Similar Problems
The Minimum Processing Time problem on Leetcode often involves optimizing task execution to minimize delays, similar to the Train Problem, where scheduling plays a crucial role. Another common challenge is the Minimum Buses problem, which deals with optimizing transportation routes, much like the Transportation Problem, where efficient allocation of resources is key. The Chocolate Problem is a classic example where techniques like Binary Search on Answer can be applied to partition resources optimally. Similarly, the Ceiling of a Number problem is a fundamental binary search concept that helps in solving threshold-based constraints efficiently. Many of these problems leverage binary search, greedy algorithms, or dynamic programming for the best possible solution.
Now we have successfully tackled this problem, let's try these similar problems.
Koko loves to eat bananas. There are n piles of bananas, the ith pile has piles[i] bananas. The guards have gone and will come back in h hours.Koko can decide her bananas-per-hour eating speed of k. Each hour, she chooses some pile of bananas and eats k bananas from that pile. If the pile has less than k bananas, she eats all of them instead and will not eat any more bananas during this hour.Koko likes to eat slowly but still wants to finish eating all the bananas before the guards return.Return the minimum integer k such that she can eat all the bananas within h hours.
2. Sort Transformed Array
We're given an array nums which is sorted in ascending order, and three integers a, b, and c. These three integers are coefficients of a quadratic function f(x) = ax^2 + bx + c. Our task is to apply this function to each element in the array and then return the array with its elements sorted after the transformation. This transformed and sorted array needs to adhere to the standard non-decreasing order.