2224. Minimum Number of Operations to Convert Time

EasyGreedyString
Leetcode Link

Problem Description

The problem presents a scenario where you are given two strings, current and correct, which represent two 24-hour formatted times, using the format "HH:MM". The HH part corresponds to the hour portion, ranging from 00 to 23, and MM is the minutes portion, ranging from 00 to 59. The goal is to find the minimum number of operations required to change the current time to the correct time. An operation is defined as adding 1, 5, 15, or 60 minutes to the current time, and you are allowed to perform as many operations as necessary to achieve the correct time.

Intuition

To solve this problem, we need to minimize the number of operations required to convert current to correct. The intuition is to use the largest possible increment (60 minutes) as many times as we can without exceeding the correct time, then proceed to the next largest (15 minutes), and so on down to the smallest increment (1 minute). This greedy approach ensures that we are always making the biggest leap towards the correct time at each step, thereby minimizing the total number of steps.

We convert both current and correct times to minutes since midnight, which makes the calculation easier since we are now dealing with integers. This is done by multiplying the hours by 60 and adding the minutes. Then, we calculate the difference d between correct and current.

Next, we use a loop to iterate over the list of increments [60, 15, 5, 1]. In each iteration, we add to ans the integer division of d by the current increment, which is the maximum number of times we can perform the current operation. We then update d to the remainder of this division to process the remaining time with the next smaller increment. This continues until we have used all permissible increments, at which point d should be 0, and ans should contain the minimum number of operations.

Learn more about Greedy patterns.

Not Sure What to Study? Take the 2-min Quiz to Find Your Missing Piece：

Which of the following shows the order of node visit in a Breadth-first Search?

Solution Approach

The implementation of the solution closely mirrors the intuition explained earlier. The algorithm is straightforward and can be broken down into the following steps:

  1. Convert both current and correct into minutes: This is the first operation in the solution which involves parsing the hour and minute components of both time strings separately, converting them to integers, multiplying the hours by 60 to get the total minutes for the hours part, and finally adding the minutes to this result. In Python, this looks like int(current[:2]) * 60 + int(current[3:]), where [:2] takes the first two characters of the string (hours) and [3:] takes the characters from the fourth to the end (minutes).

  2. Calculate the difference: We then subtract the value of current in minutes from the value of correct in minutes to get the total number of minutes that need to be added to current to reach correct. This difference is represented by d.

  3. Perform operations to minimize the time difference: Using a for loop, the solution iterates over a list [60, 15, 5, 1] which contains the allowed minute increments for the operations, in descending order.

    • Within the loop, the solution uses integer division d // i to find out how many times a particular increment can be used. It adds this number to the ans variable, which accumulates the total number of operations needed.
    • Then, d is updated to the remainder of this division with d %= i. This remainder represents the minutes that are yet to be matched and is efficiently reduced with each larger increment before moving to smaller ones.

The choice of data structures in this solution is minimal. An integer ans is used to store the cumulative count of operations, and a simple list of increments is iterated upon.

This approach is a common algorithmic pattern called the greedy algorithm, which tries to solve a problem by making the best possible decision at the current step without looking ahead to the future steps. It's called "greedy" because the decision is based on what seems to be the best immediate choice.

Lastly, the algorithm executes in O(1) time complexity since the operations are bound by a fixed number of possible increment values and the loop runs at most 4 times (once for each increment value: 60, 15, 5, and 1).

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

What are the two properties the problem needs to have for dynamic programming to be applicable? (Select 2)

Example Walkthrough

Let's walk through a simple example to illustrate the solution approach:

Suppose we have current time as "02:30" and correct time as "03:10".

  1. Convert both times to minutes:

    • The current time is converted to 150 minutes (2*60 + 30).
    • The correct time is converted to 190 minutes (3*60 + 10).

  2. Calculate the difference:

    • The difference d between correct and current is 40 minutes (190 - 150).

  3. Perform operations:

    • We start by iterating over the increments [60, 15, 5, 1].
    • We cannot use the 60-minute operation since d is less than 60.
    • For the 15-minute operation, we get 40 // 15 = 2, so we can add 15 minutes two times. ans becomes 2, and d becomes 10 (the remainder of dividing 40 by 15).
    • The 5-minute operation can be used twice on the remaining 10 minutes. Now, ans is 2 + 2 = 4, and d is 0.
    • Since d is now 0, we do not need to perform any 1-minute operations.

In this example, the minimum number of operations required to change the current time to the correct time is 4. This includes performing the 15-minute increment twice and the 5-minute increment twice.

Solution Implementation

1class Solution:
2    def convertTime(self, current: str, correct: str) -> int:
3        # Convert the 'current' time to minutes
4        current_minutes = int(current[:2]) * 60 + int(current[3:])
5      
6        # Convert the 'correct' time to minutes
7        correct_minutes = int(correct[:2]) * 60 + int(correct[3:])
8      
9        # Calculate the difference in minutes
10        delta_minutes = correct_minutes - current_minutes
11      
12        # Initialize the number of operations used
13        operations_used = 0
14      
15        # List of available operation increments in minutes
16        operation_increments = [60, 15, 5, 1]
17      
18        # For each increment option, calculate the maximum number of operations possible
19        # And then, reduce the remaining delta_minutes accordingly
20        for increment in operation_increments:
21            operations_used += delta_minutes // increment  # Perform the largest operations possible
22            delta_minutes %= increment  # Reduce delta_minutes by the amount operated on
23      
24        # Return the total number of operations used to adjust the time
25        return operations_used
26
1class Solution {
2    public int convertTime(String current, String correct) {
3        // Convert the 'current' time into minutes
4        int currentMinutes = Integer.parseInt(current.substring(0, 2)) * 60
5                           + Integer.parseInt(current.substring(3));
6      
7        // Convert the 'correct' time into minutes
8        int correctMinutes = Integer.parseInt(correct.substring(0, 2)) * 60
9                           + Integer.parseInt(correct.substring(3));
10      
11        // Initialize answer to store the number of operations required
12        int operations = 0;
13      
14        // Calculate the difference in minutes
15        int difference = correctMinutes - currentMinutes;
16      
17        // Array containing possible operations in descending order by their time value
18        Integer[] operationsArray = new Integer[] {60, 15, 5, 1};
19      
20        // Iterate over the operations array to find the minimum number
21        // of operations needed to reach the correct time
22        for (int minutesPerOperation : operationsArray) {
23            // Divide the time difference by the time value of operation
24            operations += difference / minutesPerOperation;
25          
26            // Update the difference to reflect the remaining time after performing this operation
27            difference %= minutesPerOperation;
28        }
29      
30        // Return the minimum number of operations required
31        return operations;
32    }
33}
34
1#include <string>
2#include <vector>
3
4class Solution {
5public:
6    // Function to convert time from 'current' to 'correct' using minimum operations
7    int convertTime(std::string current, std::string correct) {
8        // Convert 'current' time from hours:minutes format to minutes
9        int currentMinutes = std::stoi(current.substr(0, 2)) * 60 + std::stoi(current.substr(3, 2));
10        // Convert 'correct' time from hours:minutes format to minutes
11        int correctMinutes = std::stoi(correct.substr(0, 2)) * 60 + std::stoi(correct.substr(3, 2));
12      
13        // Calculate the difference in minutes
14        int difference = correctMinutes - currentMinutes;
15        // Variable to store the number of operations needed
16        int operationsCount = 0;
17        // Define increments in minutes that can be used to adjust the time
18        std::vector<int> increments = {60, 15, 5, 1};
19      
20        // Iterate over possible increments
21        for (int increment : increments) {
22            // Use the largest increment to reduce the difference as much as possible
23            operationsCount += difference / increment;
24            // Update the remaining difference
25            difference %= increment;
26        }
27        // Return the total number of operations required
28        return operationsCount;
29    }
30};
31
1// Import statements are not typically used in TypeScript as they are in C++
2// Instead, TypeScript uses modules and export/import syntax
3
4// Function to convert time from 'current' to 'correct' using minimum operations
5function convertTime(current: string, correct: string): number {
6    // Convert 'current' time from hours:minutes format to minutes
7    const currentMinutes: number = parseInt(current.substring(0, 2)) * 60 + parseInt(current.substring(3));
8
9    // Convert 'correct' time from hours:minutes format to minutes
10    const correctMinutes: number = parseInt(correct.substring(0, 2)) * 60 + parseInt(correct.substring(3));
11
12    // Calculate the difference in minutes
13    let difference: number = correctMinutes - currentMinutes;
14
15    // Variable to store the number of operations needed
16    let operationsCount: number = 0;
17
18    // Define increments in minutes that can be used to adjust the time
19    const increments: number[] = [60, 15, 5, 1];
20  
21    // Iterate over possible increments
22    for (const increment of increments) {
23        // Use the largest increment to reduce the difference as much as possible
24        operationsCount += Math.floor(difference / increment);
25
26        // Update the remaining difference
27        difference %= increment;
28    }
29
30    // Return the total number of operations required
31    return operationsCount;
32}
33
34// The code as per TypeScript conventions does not define global variables or methods.
35// Instead, they are typically encapsulated in modules or classes.
36// However, as per the request, this function is defined globally.
37
Not Sure What to Study? Take the 2-min Quiz：

What is the worst case running time for finding an element in a binary search tree(not necessarily balanced) of size n?

Time and Space Complexity

Time Complexity

The time complexity of this function is O(1). This is because the function performs a constant number of operations irrespective of the size of the input. The calculations performed to convert the times from string format to minutes, the loop to calculate the number of operations needed to reach the correct time, and the arithmetic operations inside the loop all execute in constant time. There are no iterative statements that depend on the input size, and the loop runs a maximum of four times (once for each value in the [60, 15, 5, 1] list).

Space Complexity

The space complexity of this function is also O(1). The function only uses a fixed amount of additional memory: the variables a, b, ans, and d hold single integer values, and the list [60, 15, 5, 1] has a fixed size. Therefore, the amount of memory used does not scale with the input size, guaranteeing constant space complexity.

Learn more about how to find time and space complexity quickly using problem constraints.

Fast Track Your Learning with Our Quick Skills Quiz:

What data structure does Breadth-first search typically uses to store intermediate states?

Recommended Readings

Greedy Introduction

Greedy Introduction iframe width 560 height 315 src https www youtube com embed WTslqPbj7I title YouTube video player frameborder 0 allow accelerometer autoplay clipboard write encrypted media gyroscope picture in picture web share allowfullscreen iframe When do we use greedy Greedy algorithms tend to solve optimization problems Typically they will ask you

LeetCode Patterns - Top Patterns for Coding Interviews

Top Patterns to Conquer the Technical Coding Interview Should the written word bore you fear not A delightful video alternative awaits iframe width 560 height 315 src https www youtube com embed LW8Io6IPYHw title YouTube video player frameborder 0 allow accelerometer autoplay clipboard write encrypted media gyroscope picture in picture

Recursion Review

Recursion Recursion is one of the most important concepts in computer science Simply speaking recursion is the process of a function calling itself Using a real life analogy imagine a scenario where you invite your friends to lunch https algomonster s3 us east 2 amazonaws com recursion jpg You first

Got a question? Ask the Teaching Assistant anything you don't understand.

Still not clear? Ask in the Forum,  Discord or Submit the part you don't understand to our editors.

←
↑TA 👨‍🏫