Difficulty: Easy | Acceptance: 66.40% | Paid: No Topics: String, Greedy
You are given two strings current and correct representing two times on a 24-hour digital clock. current and correct are in the format “HH:MM” (00 <= HH <= 23, 00 <= MM <= 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.
- Examples
- Constraints
- Greedy Approach
- Mathematical Approach
- Dynamic Programming Approach
Examples
Example 1
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.
Example 2
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
Greedy Approach
Intuition Since the allowed operations (60, 15, 5, 1) are divisors of each other, using the largest possible operation first always yields the optimal solution. This is a classic greedy coin change problem.
Steps
- Parse both time strings to get hours and minutes
- Convert both times to total minutes since midnight
- Calculate the difference in minutes
- Greedily use the largest operation (60, then 15, then 5, then 1) as many times as possible
- Count the total operations used
class Solution:
def convertTime(self, current: str, correct: str) -> int:
curr_h, curr_m = map(int, current.split(':'))
corr_h, corr_m = map(int, correct.split(':'))
curr_total = curr_h * 60 + curr_m
corr_total = corr_h * 60 + corr_m
diff = corr_total - curr_total
operations = [60, 15, 5, 1]
count = 0
for op in operations:
count += diff // op
diff %= op
return count
Complexity
- Time: O(1) - Fixed number of operations (4 iterations)
- Space: O(1) - Only using a few variables
- Notes: Optimal solution with constant time and space
Mathematical Approach
Intuition The problem can be solved mathematically using division and modulo operations. Since each operation value divides the next larger one, we can directly compute the count for each operation.
Steps
- Convert both times to total minutes
- Calculate the difference
- Use integer division and modulo to count operations: diff//60 + (diff%60)//15 + ((diff%60)%15)//5 + ((diff%60)%15)%5
class Solution:
def convertTime(self, current: str, correct: str) -> int:
curr_h, curr_m = map(int, current.split(':'))
corr_h, corr_m = map(int, correct.split(':'))
curr_total = curr_h * 60 + curr_m
corr_total = corr_h * 60 + corr_m
diff = corr_total - curr_total
# Mathematical approach using division and modulo
count = diff // 60
diff %= 60
count += diff // 15
diff %= 15
count += diff // 5
diff %= 5
count += diff
return count
Complexity
- Time: O(1) - Constant number of arithmetic operations
- Space: O(1) - Only using a few variables
- Notes: Same complexity as greedy, just expressed differently
Dynamic Programming Approach
Intuition This is a classic unbounded knapsack / coin change problem. We can use DP to find the minimum number of operations to reach each minute value from 0 to the target difference.
Steps
- Convert both times to total minutes and calculate difference
- Create a DP array where dp[i] represents minimum operations to reach i minutes
- Initialize dp[0] = 0 and others to infinity
- For each minute from 1 to diff, try all 4 operations and take minimum
class Solution:
def convertTime(self, current: str, correct: str) -> int:
curr_h, curr_m = map(int, current.split(':'))
corr_h, corr_m = map(int, correct.split(':'))
curr_total = curr_h * 60 + curr_m
corr_total = corr_h * 60 + corr_m
diff = corr_total - curr_total
operations = [1, 5, 15, 60]
dp = [float('inf')] * (diff + 1)
dp[0] = 0
for i in range(1, diff + 1):
for op in operations:
if i >= op:
dp[i] = min(dp[i], dp[i - op] + 1)
return dp[diff]
Complexity
- Time: O(n) where n is the difference in minutes (max 1439)
- Space: O(n) for the DP array
- Notes: Overkill for this problem but demonstrates the general coin change DP pattern