Minimum Number of Operations to Convert Time — Editorial

Opening the reading…

Intuitionwhy the largest usable increment is always safe

The clock format hides the quantity that matters. Once each time is written as minutes since midnight, the problem becomes choosing the fewest values from 60, 15, 5, and 1 whose sum equals the difference between the two times. The guarantee that current is no later than correct means this difference is never negative.

An operation with a larger increment can replace several smaller operations whenever it fits. Therefore, take as many 60-minute operations as possible, then as many 15-minute operations as possible, followed by 5 and finally 1. After each choice, the remainder is smaller than the increment just used, so no later choice could have replaced one of those operations with fewer operations.

Approach

Parse each HH:MM string into hours multiplied by 60 plus minutes, because arithmetic on total minutes avoids separate handling of hour and minute fields.

Subtract the current total from the correct total to obtain the number of minutes that must be added, because every operation contributes directly to this one difference.

Visit the increments 60, 15, 5, and 1 in descending order, because using the largest available increment first cannot increase the number of operations for this fixed set of divisors.

Add difference divided by increment to the answer, because that is exactly the maximum number of operations of this size that fit in the remaining difference.

Replace difference with difference modulo increment, because the quotient has already accounted for every operation of that size and only the leftover minutes still need conversion.

Return the operation count after the final increment, because increment 1 always consumes any remaining minutes exactly.

Complexitythe input size is fixed by the HH:MM format

MEASURE	BOUND	WHY
Time	O(1)	Each time is parsed from two fixed-width fields, and the loop examines exactly four increments. No operation depends on the numerical size of the time difference.
Space	O(1) extra	The conversion variables, answer, and four-element increment list use constant working memory. The returned integer is the required output and is not counted; the bound remains constant for every valid time.

No variable beyond the fixed-size time strings is needed; the bounds are constant with respect to input length.

Annotated solutionC++ · greedy quotient-and-remainder conversion

CPPParse both times, then consume the minute difference with descending increments.

#include <string>
#include <vector>

using namespace std;

class Solution {
public:
    int convertTime(string current, string correct) {
        auto toMinutes = [](const string& time) {
            return stoi(time.substr(0, 2)) * 60 + stoi(time.substr(3, 2));
        };

        int difference = toMinutes(correct) - toMinutes(current);
        int operations = 0;
        vector<int> increments = {60, 15, 5, 1};

        for (int increment : increments) {
            operations += difference / increment;
            difference %= increment;
        }

        return operations;
    }
};

The two lines inside the loop form the greedy core. The quotient counts all operations of the current size that fit, while the remainder becomes the only work left for smaller increments. Processing 60 before 15, 5, and 1 is essential: if a smaller increment were used first, the code could spend several operations on minutes that one larger operation would have covered.