# Minimum Number of Operations to Convert Time **Difficulty:** EASY [External](https://leetcode.com/problems/minimum-number-of-operations-to-convert-time) Canonical: https://scaleengineer.com/dsa/problems/minimum-number-of-operations-to-convert-time **Patterns:** [Greedy](https://scaleengineer.com/dsa/patterns/greedy) **Data structures:** String --- ## Problem 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 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` # Approaches ## Dynamic Programming This approach treats the problem as a variation of the classic "Coin Change" problem. We want to find the minimum number of "coins" (operations of 1, 5, 15, 60 minutes) that sum up to the total difference in minutes between the `correct` and `current` time. Dynamic programming provides a systematic way to solve this by building up the solution for all differences from 1 up to the target difference. **Time:** O(D), where D is the total difference in minutes. The outer loop runs D times, and the inner loop is constant (4 iterations), making the complexity linear with respect to the minute difference. · **Space:** O(D), where D is the total difference in minutes. The maximum possible difference is from "00:00" to "23:59", which is 1439 minutes. This space is required for the DP table. **Pros:** Guaranteed to find the optimal solution for any set of operations (coins).; It's a general and robust method for this type of minimization problem. **Cons:** Requires O(D) extra space for the DP array, where D is the minute difference.; Slower than the greedy approach for this specific problem.; It's a more complex solution than necessary given that a greedy approach is optimal. ### Explanation First, we convert the input time strings (`current` and `correct`) from the "HH:MM" format into a single integer representing the total number of minutes from midnight (00:00). Then, we calculate the total difference in minutes, `diff = correct_minutes - current_minutes`. We create a dynamic programming array, `dp`, of size `diff + 1`, where `dp[i]` will store the minimum number of operations required to achieve a time difference of `i` minutes. We initialize `dp[0] = 0` (0 minutes difference requires 0 operations) and all other `dp[i]` to a large value. We then iterate from `i = 1` to `diff`. For each `i`, we calculate `dp[i]` by considering all possible last operations (1, 5, 15, or 60 minutes). The recurrence relation is `dp[i] = 1 + min(dp[i-op])` for each `op` in `{1, 5, 15, 60}`, provided `i >= op`. The final answer is `dp[diff]`. ```java class Solution { public int convertTime(String current, String correct) { // 1. Convert times to minutes int currentMinutes = Integer.parseInt(current.substring(0, 2)) * 60 + Integer.parseInt(current.substring(3, 5)); int correctMinutes = Integer.parseInt(correct.substring(0, 2)) * 60 + Integer.parseInt(correct.substring(3, 5)); int diff = correctMinutes - currentMinutes; if (diff == 0) { return 0; } // 2. DP setup int[] dp = new int[diff + 1]; java.util.Arrays.fill(dp, Integer.MAX_VALUE); dp[0] = 0; int[] operations = {1, 5, 15, 60}; // 3. Fill DP table for (int i = 1; i <= diff; i++) { for (int op : operations) { if (i >= op && dp[i - op] != Integer.MAX_VALUE) { dp[i] = Math.min(dp[i], 1 + dp[i - op]); } } } // 4. Return result return dp[diff]; } } ``` ### Algorithm * Parse the `current` and `correct` time strings to get the total minutes from midnight for each, let's call them `startMinutes` and `endMinutes`. * Calculate the total difference in minutes: `diff = endMinutes - startMinutes`. * If `diff` is 0, no operations are needed, so return 0. * Create a dynamic programming array, `dp`, of size `diff + 1`. `dp[i]` will store the minimum number of operations to achieve a time difference of `i` minutes. * Initialize `dp[0] = 0` and all other elements of `dp` to a very large value (representing infinity). * Define the set of possible operations: `ops = {1, 5, 15, 60}`. * Iterate from `i = 1` to `diff`: * For each `i`, iterate through each operation `op` in `ops`. * If `i` is greater than or equal to `op`, it's possible to use this operation. Update `dp[i]` with the minimum of its current value and `1 + dp[i - op]`. * The final answer is the value stored in `dp[diff]`. ## Greedy Algorithm This problem has a special property that allows for a greedy solution. The set of available operations {60, 15, 5, 1} forms a system where always choosing the largest possible operation to reduce the remaining time difference leads to the minimum total number of operations. This is because each operation value is a multiple of the smaller ones (or can be optimally constructed from them), preventing a situation where using smaller operations would be better. This approach is much more efficient than dynamic programming. **Time:** O(1). The time taken to parse the strings and perform the few arithmetic operations is constant and does not depend on the magnitude of the input times. · **Space:** O(1). We only use a few variables to store the minutes, difference, and operation count, requiring constant extra space. **Pros:** Extremely fast and efficient.; Simple to understand and implement.; Requires minimal memory (constant space). **Cons:** The greedy strategy is not universally applicable to all "coin change" type problems. It works here due to the specific properties of the operation values, but one must be careful to prove its correctness before applying it. ### Explanation The most efficient way to solve this problem is with a greedy algorithm. First, we parse the time strings "HH:MM" into total minutes from midnight. We calculate the difference in minutes, `diff`, between the `correct` and `current` times. The core idea is to satisfy this difference using the fewest operations possible. To do this, we should always use the largest available time increment that is less than or equal to the remaining difference. We start with the 60-minute operation, calculating how many times we can apply it (`diff / 60`). We add this count to our total operations and update the difference to the remainder (`diff % 60`). We then repeat this process for the 15-minute, 5-minute, and finally 1-minute operations. This greedy choice is optimal for this specific set of operations. ```java class Solution { public int convertTime(String current, String correct) { // 1. Convert times to minutes int currentMinutes = Integer.parseInt(current.substring(0, 2)) * 60 + Integer.parseInt(current.substring(3, 5)); int correctMinutes = Integer.parseInt(correct.substring(0, 2)) * 60 + Integer.parseInt(correct.substring(3, 5)); int diff = correctMinutes - currentMinutes; int operationsCount = 0; // 2. Greedily apply operations from largest to smallest operationsCount += diff / 60; diff %= 60; operationsCount += diff / 15; diff %= 15; operationsCount += diff / 5; diff %= 5; operationsCount += diff; // Remaining diff is handled by 1-minute operations return operationsCount; } } ``` ### Algorithm * Parse the `current` and `correct` time strings to get the total minutes from midnight for each, let's call them `startMinutes` and `endMinutes`. * Calculate the total difference in minutes that needs to be covered: `diff = endMinutes - startMinutes`. * Initialize a counter for the number of operations, `operationsCount`, to zero. * To minimize the number of operations, greedily use the largest possible increments first. Process the operations in descending order: 60, 15, 5, and 1. * For the 60-minute operation: add `diff / 60` to `operationsCount` and update `diff` to the remainder, `diff %= 60`. * For the 15-minute operation: add `diff / 15` to `operationsCount` and update `diff` to `diff %= 15`. * For the 5-minute operation: add `diff / 5` to `operationsCount` and update `diff` to `diff %= 5`. * For the 1-minute operation: the remaining `diff` must be covered by 1-minute operations. Add `diff` to `operationsCount`. * Return the final `operationsCount`. # Solutions ### Java ```java class Solution { public int convertTime(String current, String correct) { int a = Integer.parseInt(current.substring(0, 2)) * 60 + Integer.parseInt(current.substring(3)); int b = Integer.parseInt(correct.substring(0, 2)) * 60 + Integer.parseInt(correct.substring(3)); int ans = 0, d = b - a; for (int i : Arrays.asList(60, 15, 5, 1)) { ans += d / i; d %= i; } return ans; } } ``` ### Python ```python class Solution: def convertTime(self, current: str, correct: str) -> int: a = int(current[: 2]) * 60 + int(current[3:]) b = int(correct[: 2]) * 60 + int(correct[3:]) ans, d = 0, b - a for i in [60, 15, 5, 1]: ans += d // i d %= i return ans ``` ### CPP ```cpp class Solution { public: int convertTime(string current, string correct) { int a = stoi(current.substr(0, 2)) * 60 + stoi(current.substr(3, 2)); int b = stoi(correct.substr(0, 2)) * 60 + stoi(correct.substr(3, 2)); int ans = 0, d = b - a; vector inc = {60, 15, 5, 1}; for (int i : inc) { ans += d / i; d %= i; } return ans; } }; ```