Minimum Number of Operations to Convert Time
Problem Description
You are given two strings current and correct representing two 24-hour times.
24-hour times are formatted as "HH:MM", where HH is between 00 and 23, and MM is between 00 and 59. The earliest 24-hour time is 00:00, and the latest is 23:59.
In one operation, you can increase the time current by 1, 5, 15, or 60 minutes. You can perform this operation any number of times.
Return the minimum number of operations needed to convert current to correct.
Example
Input: current = "02:30", correct = "04:35"
Output: 3
Explanation: We can convert current to correct in 3 operations as follows:
- Add 60 minutes to current. current becomes "03:30".
- Add 60 minutes to current. current becomes "04:30".
- Add 5 minutes to current. current becomes "04:35".
It can be proven that it is not possible to convert current to correct in fewer than 3 operations.
Input: current = "11:00", correct = "11:01"
Output: 1
Explanation: We only have to add one minute to current, so the minimum number of operations needed is 1.
Constraints
- current and correct are in the format "HH:MM"
- current <= correct
When solving problems where we aim to maximize or minimize results or operations, it's key to make the best possible choice at every step—this approach is known as the Greedy Technique. In this problem, we're in a similar situation, where choosing the optimal option at each point (increasing current time just enough to satisfy the correct time with the least number of operations) can lead to the best solution. Let's dive into thinking of a greedy approach for this!
Optimal Approach
Intuition
To solve this problem, the key is to focus on converting the current time into the correct time using the fewest possible operations. A simple way to think about time is to convert it from hours and minutes into a single unit—total minutes from the start of the day. Converting time into total minutes simplifies the problem, as the allowed increments (60, 15, 5, and 1 minutes) are all in minutes. Instead of dealing with two parts (hours and minutes), we treat the time as a single number. This makes it easier to calculate the exact difference between the current and correct times, and we can focus on reducing this difference without worrying about the hour-minute structure.
For example, if current = "02:30" and correct = "05:45", we can represent them as 150 minutes and 345 minutes, respectively. The difference between them, 345 - 150 = 195 minutes, represents the total time we need to add to make the two times match. Once we have this difference, the goal is to reduce it to zero in as few steps as possible.
Now, consider the allowed operations: adding 1, 5, 15, or 60 minutes. To minimize the number of steps, we need to reduce the difference by the largest possible increment at each step. This is the essence of a greedy strategy—always making the choice that provides the biggest progress while staying within the rules. For example, if the difference is 195, we start by subtracting as many chunks of 60 minutes as possible. Here, 3 steps of 60 minutes reduce the difference to 195 - 180 = 15. Then, since 15 minutes is an allowed increment, we add it in one step. In total, we’ve used 4 operations: three increments of 60 minutes and one increment of 15 minutes. This is the optimal solution because each step made the maximum possible progress.
This greedy approach works because it ensures that we reduce the remaining difference as quickly as possible. If we were to use smaller increments unnecessarily (e.g., adding 1 minute repeatedly), it would take far more operations to reach the target. By always choosing the largest increment that fits the difference, we minimize the number of steps while ensuring we don’t overshoot the goal. This strategy guarantees the optimal solution in the most intuitive and efficient way.
Approach
Step 1: Convert Time to Minutes
We need to convert both the current and correct times into total minutes from the start of the day. To do this:
- Extract the hours and minutes from both times (which are given in "HH:MM" format).
- Convert the hours into minutes and add the minutes value.
- Store the results for current and correct times in variables currentTime and correctTime.
How to convert given time into minutes?
To convert time from the format "HH:MM" to minutes, you need to break down the string into hours (HH) and minutes (MM), then calculate the total minutes. Here's the step-by-step explanation:
Extract the Hours:
- The time is given in the format "HH:MM". The first two characters represent the hours.
- The first character (current[0]) represents the tens place of the hours.
- The second character (current[1]) represents the ones place of the hours.
- To convert the hours into minutes, multiply the tens place of the hours by 10 and then multiply by 60 (since there are 60 minutes in an hour).
- Multiply the ones place of the hours by 60 to convert it to minutes.
Extract the Minutes:
- The last two characters represent the minutes.
- The third character (current[3]) represents the tens place of the minutes.
- The fourth character (current[4]) represents the ones place of the minutes.
- To convert the minutes into total minutes, multiply the tens place of the minutes by 10, and add the ones place of the minutes directly.
Calculate Total Minutes: Add the results of the hours and minutes to get the total time in minutes.
Example Conversion
For current = "02:30", we follow these steps:
- Hours: The first character current[0] is '0' and the second character current[1] is '2'. Convert hours to minutes: (0 * 10 * 60) + (2 * 60) = 0 + 120 = 120 minutes.
- Minutes: The third character current[3] is '3' and the fourth character current[4] is '0'. Convert minutes to minutes: (3 * 10) + 0 = 30 minutes.
- Total time: 120 minutes + 30 minutes = 150 minutes.
Step 2: Calculate the Difference
Find the difference between correctTime and currentTime to get the number of minutes required to make the current time equal to the correct time. Store this difference in a variable called diff.
Step 3: Reduce the Difference to 0
To minimize the number of operations, we break down the difference (diff) using the largest possible increments first. We perform the following steps:
- First, we check if diff is greater than or equal to 60 minutes. If so, we divide diff by 60 to determine how many 60-minute increments can be made. We add this quotient to count, then update diff by taking the remainder after division (diff % 60).
- Next, we check if diff is greater than or equal to 15 minutes. If so, we divide diff by 15 to determine how many 15-minute increments can be made. We add this quotient to count, then update diff by taking the remainder after division (diff % 15).
- Then, we check if diff is greater than or equal to 5 minutes. If so, we divide diff by 5 to determine how many 5-minute increments can be made. We add this quotient to count, then update diff by taking the remainder after division (diff % 5).
- Finally, if diff is less than 5, we simply subtract 1 minute from diff for each remaining minute, adding the number of subtractions to count.
How does this work?
To reduce the difference (diff) to zero in the least number of steps, we first check if the difference is 60 minutes or more. If it is, we divide the difference by 60 to find out how many 60-minute steps can be made. The result of this division is added to the counter (count), and then we use the modulo operation (diff % 60) to find the leftover minutes after removing the 60-minute steps. This remainder becomes the new value of diff. Next, we check if the remaining difference is 15 minutes or more, and if so, we divide it by 15 to find how many 15-minute steps we can take. We again update the counter and use modulo (diff % 15) to get the remainder. We repeat this process for 5-minute steps and then 1-minute steps. The modulo operation helps us find the leftover minutes after taking the largest possible step, and division tells us how many times we can make that step. This ensures we make the fewest subtractions to reach zero, and the counter (count) keeps track of the total number of steps required.
Step 4: Return the Result
Once the difference becomes 0, return the count as the result, which represents the minimum number of operations needed to convert the current time to the correct time.
How do we handle times that cross over midnight?
For example, what if current = "23:50" and correct = "00:10"?
Crossing midnight is handled naturally when converting times to total minutes. For 23:50, the total minutes are 1430, and for 00:10, the total minutes are 10. If current is larger than correct, we assume the next day’s time, so we add 1440 minutes (24 hours) to correct. In this case, the difference is 1450 - 1430 = 20, and we proceed with the same greedy strategy.
Dry Run
Initial State:
current = "02:30"
correct = "04:35"
currentTime = 0, correctTime = 0, diff = 0, count = 0
Step 1: Convert current time and correct time to total minutes
currentTime is calculated by converting "02:30" into minutes:
- The hours (02) are converted to minutes: (2 * 60) = 120
- The minutes (30) are added: 120 + 30 = 150
currentTime = 150 minutes
correctTime is calculated by converting "04:35" into minutes:
- The hours (04) are converted to minutes: (4 * 60) = 240
- The minutes (35) are added: 240 + 35 = 275
correctTime = 275 minutes
Step 2: Calculate the difference between correctTime and currentTime
diff = correctTime - currentTime = 275 - 150 = 125 minutes
Step 3: Calculate the number of operations for each time increment
First, we handle the 60-minute increments:
- diff = 125, divide by 60: 125 / 60 = 2 (we can subtract 60 minutes twice)
- count is incremented by 2: count = 2
- The remainder after subtracting 2 * 60 is 125 % 60 = 5
Next, we handle the 15-minute increments:
- diff = 5, divide by 15: 5 / 15 = 0 (we cannot subtract 15 minutes)
- count remains the same: count = 2
- The remainder is 5 % 15 = 5
Next, we handle the 5-minute increments:
- diff = 5, divide by 5: 5 / 5 = 1 (we can subtract 5 minutes once)
- count is incremented by 1: count = 3
- The remainder after subtracting 5 is 5 % 5 = 0
Step 4: Return the total number of operations
At this point, diff is 0, and the total count of operations is 3.
Final State:
diff = 0
count = 3
Final Output: 3
Code for All Languages
C++
// Solution class containing the main logic
class Solution {
public:
int convertTime(string current, string correct) {
// Variable to store the current time in total minutes
int currentTime = 0;
// Variable to store the correct time in total minutes
int correctTime = 0;
// Convert the current time from HH:MM format to total minutes
currentTime = (current[0] - '0') * 10 * 60 + (current[1] - '0') * 60 + (current[3] - '0') * 10 + (current[4] - '0');
// Convert the correct time from HH:MM format to total minutes
correctTime = (correct[0] - '0') * 10 * 60 + (correct[1] - '0') * 60 + (correct[3] - '0') * 10 + (correct[4] - '0');
// Calculate the difference in minutes between currentTime and correctTime
int diff = correctTime - currentTime;
// Variable to store the minimum number of operations required
int count = 0;
// Calculate the number of operations for each time increment
// Divide by 60 to find how many 60-minute increments can be made
count += diff / 60;
diff = diff % 60;
// Divide by 15 to find how many 15-minute increments can be made
count += diff / 15;
diff = diff % 15;
// Divide by 5 to find how many 5-minute increments can be made
count += diff / 5;
diff = diff % 5;
// Divide by 1 if no larger increments are possible
count += diff;
// Return the total number of operations
return count;
}
};Java
// Solution class containing the main logic
class Solution {
public int convertTime(String current, String correct) {
// Variable to store the current time in total minutes
int currentTime = 0;
// Variable to store the correct time in total minutes
int correctTime = 0;
// Convert the current time from HH:MM format to total minutes
currentTime = (current.charAt(0) - '0') * 10 * 60 +
(current.charAt(1) - '0') * 60 +
(current.charAt(3) - '0') * 10 +
(current.charAt(4) - '0');
// Convert the correct time from HH:MM format to total minutes
correctTime = (correct.charAt(0) - '0') * 10 * 60 +
(correct.charAt(1) - '0') * 60 +
(correct.charAt(3) - '0') * 10 +
(correct.charAt(4) - '0');
// Calculate the difference in minutes between currentTime and correctTime
int diff = correctTime - currentTime;
// Variable to store the minimum number of operations required
int count = 0;
// Calculate the number of operations for each time increment
// Divide by 60 to find how many 60-minute increments can be made
count += diff / 60;
diff = diff % 60;
// Divide by 15 to find how many 15-minute increments can be made
count += diff / 15;
diff = diff % 15;
// Divide by 5 to find how many 5-minute increments can be made
count += diff / 5;
diff = diff % 5;
// Add the remaining 1 minute increments
count += diff;
// Return the total number of operations
return count;
}
}Python
# Solution class containing the main logic
class Solution:
def convertTime(self, current: str, correct: str) -> int:
# Variable to store the current time in total minutes
currentTime = (int(current[0]) * 10 + int(current[1])) * 60 + \
(int(current[3]) * 10 + int(current[4]))
# Variable to store the correct time in total minutes
correctTime = (int(correct[0]) * 10 + int(correct[1])) * 60 + \
(int(correct[3]) * 10 + int(correct[4]))
# Calculate the difference in minutes between currentTime and correctTime
diff = correctTime - currentTime
# Variable to store the minimum number of operations required
count = 0
# Calculate the number of operations for each time increment
# Divide by 60 to find how many 60-minute increments can be made
count += diff // 60
diff = diff % 60
# Divide by 15 to find how many 15-minute increments can be made
count += diff // 15
diff = diff % 15
# Divide by 5 to find how many 5-minute increments can be made
count += diff // 5
diff = diff % 5
# Add the remaining 1-minute increments
count += diff
# Return the total number of operations
return count
Javascript
// Function to calculate the minimum number of operations
var convertTime = function (current, correct) {
// Convert the current time to total minutes from the start of the day
let currentTime = (parseInt(current[0]) * 10 + parseInt(current[1])) * 60 +
(parseInt(current[3]) * 10 + parseInt(current[4]));
// Convert the correct time to total minutes from the start of the day
let correctTime = (parseInt(correct[0]) * 10 + parseInt(correct[1])) * 60 +
(parseInt(correct[3]) * 10 + parseInt(correct[4]));
// Calculate the difference in minutes between currentTime and correctTime
let diff = correctTime - currentTime;
// Variable to store the minimum number of operations required
let count = 0;
// Calculate the number of operations for each time increment
count += Math.floor(diff / 60); // Calculate number of 60-minute operations
diff %= 60; // Update the remaining difference
count += Math.floor(diff / 15); // Calculate number of 15-minute operations
diff %= 15; // Update the remaining difference
count += Math.floor(diff / 5); // Calculate number of 5-minute operations
diff %= 5; // Update the remaining difference
count += diff; // Add the remaining 1-minute operations
// Return the total number of operations
return count;
};Time Complexity : O(1)
Time Conversion: O(1)
Converting the current and correct times from the HH:MM format to total minutes involves a fixed number of operations: extracting individual digits, multiplying by powers of 10, and adding them together. These operations are constant and do not depend on the size of the input. Therefore, the time complexity for the time conversion is O(1).
Division and Modulus Operations: O(1)
The code performs a constant number of operations (division and modulus) to calculate the required number of operations for each time increment (60, 15, 5, and 1 minute). Each of these operations is executed only once for each time difference, making them O(1).
Final Time Complexity: O(1)
Since both the time conversion and the subsequent operations (division and modulus) take constant time, the overall time complexity is constant, O(1). The input size does not affect the time complexity, as there is no iteration over arrays or large inputs.
Space Complexity : O(1)
Auxiliary Space Complexity: O(1)
The auxiliary space refers to the extra space used by the algorithm apart from the input. In this case, we are only using a few variables:
- currentTime and correctTime for storing the converted time in minutes.
- diff to calculate and store the difference between the times.
- count to keep track of the number of operations required.
These variables require constant space, resulting in an auxiliary space complexity of O(1).
Total Space Complexity: O(1)
The total space includes both the input, output, and the auxiliary space.
The input strings current and correct are given as part of the input and do not contribute to the algorithm's space usage. The algorithm does not use any additional space proportional to the size of the input. Therefore, the total space complexity is O(1).
Learning Tip
Now we have successfully tackled this problem, let's try these similar problems.
A circular typewriter has letters 'a' to 'z', and the pointer starts at 'a'. Each second, you can move the pointer clockwise or counterclockwise by one step or type the current character. Given a string word, calculate the minimum seconds needed to type it by minimizing movement for each character.
You are given a 0-indexed integer array nums and an integer k. Your task is to perform the following operation exactly k times in order to maximize your score
1. Select an element m from nums.
2. Remove the selected element m from the array.
3. Add a new element with a value of m + 1 to the array.
4. Increase your score by m.