algoadvance

Leetcode 2224. Minimum Number of Operations to Convert Time

Problem Statement

You are given two strings current and correct representing two 24-hour times in the format “HH:MM.” The task is to determine the minimum number of operations required to convert current to correct. You can only perform the following operations:

  1. Add 1 minute.
  2. Add 5 minutes.
  3. Add 15 minutes.
  4. Add 60 minutes.

Return the minimum number of operations needed to transform current into correct.

Clarifying Questions

  1. Input Constraints:
    • Is it guaranteed that current and correct will be valid 24-hour format times?
    • Can current and correct be the same initial times?
  2. Output Range:
    • What is the range of operation counts we should expect to handle?
  3. Edge Cases:
    • Are there any edge cases such as transitioning from one day to the next (i.e., from 23:59 to 00:00)?

Strategy

  1. Convert Time to Minutes:
    • Convert both current and correct times into the total number of minutes past midnight for easier comparison and manipulation.
  2. Calculate Difference:
    • Determine the difference in minutes between the current and correct times.
  3. Minimize Operations:
    • Use a greedy approach to minimize the number of operations. Start with the largest allowable operation (60 minutes), then 15 minutes, then 5 minutes, and finally 1 minute. This will reduce the difference in the fewest number of steps.

Code

Here is the C++ code implementing the above strategy:

#include <iostream>
#include <string>
#include <cmath>

int convertTime(const std::string& current, const std::string& correct) {
    // Helper function to convert "HH:MM" time format to minutes past midnight.
    auto toMinutes = [](const std::string& time) {
        int hours = std::stoi(time.substr(0, 2));
        int minutes = std::stoi(time.substr(3, 2));
        return hours * 60 + minutes;
    };

    int currentMinutes = toMinutes(current);
    int correctMinutes = toMinutes(correct);

    int difference = std::abs(correctMinutes - currentMinutes);  // Ensure non-negative difference

    int operations = 0;
    int increments[] = {60, 15, 5, 1};  // Available increments

    // Apply the maximum possible increment each time
    for (int inc : increments) {
        operations += difference / inc;
        difference %= inc;
    }

    return operations;
}

// For test purposes
int main() {
    std::string current = "02:30";
    std::string correct = "04:35";
    std::cout << "Minimum operations: " << convertTime(current, correct) << std::endl;
    return 0;
}

Time Complexity

The time complexity of this solution is O(1) because the number of operations is bounded by a constant (4 different increments) regardless of the input size. The main work — converting times and calculating operations — involves simple arithmetic and remains constant time.

By following this strategy, we ensure an optimal, efficient solution to convert the given time in the fewest number of operations.

Cut your prep time in half and DOMINATE your interview with AlgoAdvance AI