Minimum Cost to Set Cooking Time

Med

#1969Time: O(1) - The main loop runs a fixed number of times (10,000 iterations). Inside the loop, all operations (arithmetic, string conversion, and cost calculation for a string of at most 4 characters) take constant time. While technically O(1), the constant factor is large compared to the optimal approach.Space: O(1) - The space required is constant as we only need a few variables to store the minimum cost and loop counters.1 company

Patterns

Math Enumeration

Companies

GE Digital

Prompt

A generic microwave supports cooking times for:

at least 1 second.
at most 99 minutes and 99 seconds.

To set the cooking time, you push at most four digits. The microwave normalizes what you push as four digits by prepending zeroes. It interprets the first two digits as the minutes and the last two digits as the seconds. It then adds them up as the cooking time. For example,

You push 9 5 4 (three digits). It is normalized as 0954 and interpreted as 9 minutes and 54 seconds.
You push 0 0 0 8 (four digits). It is interpreted as 0 minutes and 8 seconds.
You push 8 0 9 0. It is interpreted as 80 minutes and 90 seconds.
You push 8 1 3 0. It is interpreted as 81 minutes and 30 seconds.

You are given integers startAt, moveCost, pushCost, and targetSeconds. Initially, your finger is on the digit startAt. Moving the finger above any specific digit costs moveCost units of fatigue. Pushing the digit below the finger once costs pushCost units of fatigue.

There can be multiple ways to set the microwave to cook for targetSeconds seconds but you are interested in the way with the minimum cost.

Return the minimum cost to set targetSeconds seconds of cooking time.

Remember that one minute consists of 60 seconds.

Example 1:

Input: startAt = 1, moveCost = 2, pushCost = 1, targetSeconds = 600
Output: 6
Explanation: The following are the possible ways to set the cooking time.
- 1 0 0 0, interpreted as 10 minutes and 0 seconds.
  The finger is already on digit 1, pushes 1 (with cost 1), moves to 0 (with cost 2), pushes 0 (with cost 1), pushes 0 (with cost 1), and pushes 0 (with cost 1).
  The cost is: 1 + 2 + 1 + 1 + 1 = 6. This is the minimum cost.
- 0 9 6 0, interpreted as 9 minutes and 60 seconds. That is also 600 seconds.
  The finger moves to 0 (with cost 2), pushes 0 (with cost 1), moves to 9 (with cost 2), pushes 9 (with cost 1), moves to 6 (with cost 2), pushes 6 (with cost 1), moves to 0 (with cost 2), and pushes 0 (with cost 1).
  The cost is: 2 + 1 + 2 + 1 + 2 + 1 + 2 + 1 = 12.
- 9 6 0, normalized as 0960 and interpreted as 9 minutes and 60 seconds.
  The finger moves to 9 (with cost 2), pushes 9 (with cost 1), moves to 6 (with cost 2), pushes 6 (with cost 1), moves to 0 (with cost 2), and pushes 0 (with cost 1).
  The cost is: 2 + 1 + 2 + 1 + 2 + 1 = 9.

Example 2:

Input: startAt = 0, moveCost = 1, pushCost = 2, targetSeconds = 76
Output: 6
Explanation: The optimal way is to push two digits: 7 6, interpreted as 76 seconds.
The finger moves to 7 (with cost 1), pushes 7 (with cost 2), moves to 6 (with cost 1), and pushes 6 (with cost 2). The total cost is: 1 + 2 + 1 + 2 = 6
Note other possible ways are 0076, 076, 0116, and 116, but none of them produces the minimum cost.

Constraints:

0 <= startAt <= 9
1 <= moveCost, pushCost <= 10⁵
1 <= targetSeconds <= 6039

Approaches

2 approaches with complexity analysis and trade-offs.

This approach involves generating every possible sequence of digits that can be typed into the microwave, checking if it results in the targetSeconds, and calculating the cost if it does. Since the input is at most four digits, we can generate all number strings corresponding to numbers from 0 to 9999.

Algorithm

Initialize minCost to a very large value.
Create a helper function calculateCost(string, startAt, moveCost, pushCost) to compute the cost of typing a sequence of digits.
Loop through all possible numerical inputs i from 0 to 9999. These represent all possible typed strings of up to 4 digits.
For each i:
- The microwave normalizes this input by prepending zeros to make it 4 digits. The first two digits become minutes and the last two become seconds. This is equivalent to minutes = i / 100 and seconds = i % 100.
- Check if the interpreted minutes and seconds are valid (i.e., not exceeding 99). If minutes > 99 or seconds > 99, this input is invalid, so we skip it.
- Calculate the total time in seconds: totalSeconds = minutes * 60 + seconds.
- If totalSeconds equals targetSeconds:
  - This input i is a valid way to set the time.
  - Convert i to its string representation, timeStr.
  - Calculate the cost of typing timeStr using the helper function.
  - Update minCost with the minimum cost found so far.
After checking all numbers up to 9999, return minCost.

Walkthrough

The core idea is to simulate the process from the user's perspective: trying every possible input. We can iterate through all numbers from 0 to 9999, which covers all inputs from one to four digits (e.g., 8, 76, 954, 1000). For each number, we determine the time it sets on the microwave based on the given normalization and interpretation rules. If this time matches the targetSeconds, we calculate the cost of typing that number and update our overall minimum cost. This method is exhaustive and guarantees finding a solution if one exists within the 4-digit input limit.

Complexity

Time

O(1) - The main loop runs a fixed number of times (10,000 iterations). Inside the loop, all operations (arithmetic, string conversion, and cost calculation for a string of at most 4 characters) take constant time. While technically O(1), the constant factor is large compared to the optimal approach.

Space

O(1) - The space required is constant as we only need a few variables to store the minimum cost and loop counters.

Trade-offs

Pros

The logic is straightforward and directly models the problem of trying all inputs.
It is guaranteed to find the minimum cost because it explores the entire search space of possible inputs.

Cons

This approach is inefficient as it checks a large number of possibilities (10,000 inputs), most of which will not result in the targetSeconds.

Instead of checking all possible inputs, a more efficient method is to work backward from the targetSeconds. We can determine all valid combinations of minutes and seconds that add up to the target time. For each valid combination, we then construct the most efficient sequence of digits to type and calculate its cost. The minimum of these costs will be the answer.

Algorithm

Initialize minCost to a very large value.
Create a helper function calculateCost(string, startAt, moveCost, pushCost) that calculates the cost of typing a given string of digits.
Iterate through all possible minutes from 0 to 99.
For each minutes value, calculate the required seconds using the formula: seconds = targetSeconds - minutes * 60.
Check if the calculated seconds value is valid (i.e., between 0 and 99, inclusive).
If seconds is valid, we have found a valid (minutes, seconds) combination:
- Construct the string timeStr that needs to be typed. It has been proven that typing leading zeros is always more expensive, so we construct the shortest possible string.
- If minutes == 0, the string is simply the string representation of seconds (e.g., 76).
- If minutes > 0, the string is the string representation of minutes followed by the two-digit string representation of seconds (e.g., for 9 min 60 sec, type 960; for 10 min 0 sec, type 1000). This can be formed by String.valueOf(minutes) + String.format("%02d", seconds).
- Calculate the cost of typing timeStr using the helper function.
- Update minCost = min(minCost, currentCost).
After iterating through all possible minutes, return the final minCost.

Walkthrough

This approach narrows down the search space significantly. We know that targetSeconds = minutes * 60 + seconds. We can iterate through all possible values for minutes (0 to 99) and calculate the corresponding seconds. If the calculated seconds is also in the valid range (0 to 99), we have a valid pair. For each such (minutes, seconds) pair, we determine the optimal string to type. It can be shown that typing leading zeros is never optimal, so we only need to consider the shortest string representation (e.g., 76 instead of 076, 960 instead of 0960). We calculate the cost for each of these optimal strings and find the minimum among them. Since the number of possible minutes is small (100), this approach is very fast.

1class Solution {2    public int minCostToSetTime(int startAt, int moveCost, int pushCost, int targetSeconds) {3        long minCost = Long.MAX_VALUE;4        5        // Iterate through all possible minutes from 0 to 996        for (int minutes = 0; minutes <= 99; minutes++) {7            int seconds = targetSeconds - minutes * 60;8            9            // Check if the calculated seconds are valid (0-99)10            if (seconds >= 0 && seconds <= 99) {11                // Construct the string to be typed.12                String timeStr;13                if (minutes == 0) {14                    timeStr = Integer.toString(seconds);15                } else {16                    timeStr = Integer.toString(minutes) + String.format("%02d", seconds);17                }18                19                minCost = Math.min(minCost, calculateCost(timeStr, startAt, moveCost, pushCost));20            }21        }22        return (int) minCost;23    }24 25    private long calculateCost(String s, int startAt, int moveCost, int pushCost) {26        long cost = 0;27        int currentPos = startAt;28        for (char c : s.toCharArray()) {29            int digit = c - '0';30            if (digit != currentPos) {31                cost += moveCost;32                currentPos = digit;33            }34            cost += pushCost;35        }36        return cost;37    }38}

Complexity

Time

O(1) - The loop runs at most 100 times, and all operations within the loop take constant time. This is the optimal time complexity.

Space

O(1) - The space used is constant, only requiring a few variables for calculations.

Trade-offs

Pros

Highly efficient as it avoids unnecessary computations by only considering valid (minutes, seconds) combinations.
The search space is very small (at most 100 combinations to check), leading to a very fast solution.

Cons

The logic for constructing the correct string to type from a (minutes, seconds) pair requires careful thought and understanding of the problem's rules.

Solutions

Solution

1class Solution {2public3  int minCostSetTime(int startAt, int moveCost, int pushCost,4                     int targetSeconds) {5    int m = targetSeconds / 60;6    int s = targetSeconds % 60;7    return Math.min(f(m, s, startAt, moveCost, pushCost),8                    f(m - 1, s + 60, startAt, moveCost, pushCost));9  }10private11  int f(int m, int s, int prev, int moveCost, int pushCost) {12    if (m < 0 || m > 99 || s < 0 || s > 99) {13      return Integer.MAX_VALUE;14    }15    int[] arr = new int[]{m / 10, m % 10, s / 10, s % 10};16    int i = 0;17    for (; i < 4 && arr[i] == 0; ++i)18      ;19    int t = 0;20    for (; i < 4; ++i) {21      if (arr[i] != prev) {22        t += moveCost;23      }24      t += pushCost;25      prev = arr[i];26    }27    return t;28  }29}

1class Solution {2public:3  int minCostSetTime(int startAt, int moveCost, int pushCost,4                     int targetSeconds) {5    int m = targetSeconds / 60, s = targetSeconds % 60;6    return min(f(m, s, startAt, moveCost, pushCost),7               f(m - 1, s + 60, startAt, moveCost, pushCost));8  }9  int f(int m, int s, int prev, int moveCost, int pushCost) {10    if (m < 0 || m > 99 || s < 0 || s > 99)11      return INT_MAX;12    vector<int> arr = {m / 10, m % 10, s / 10, s % 10};13    int i = 0;14    for (; i < 4 && arr[i] == 0; ++i)15      ;16    int t = 0;17    for (; i < 4; ++i) {18      if (arr[i] != prev)19        t += moveCost;20      t += pushCost;21      prev = arr[i];22    }23    return t;24  }25};

1class Solution:2    def minCostSetTime(self, startAt: int, moveCost: int, pushCost: int, targetSeconds: int) -> int: def f(m, s): if not 0 <= m < 100 or not 0 <= s < 100: return inf arr = [m // 10, m % 10, s // 10, s % 10] i = 0 while i < 4 and arr[i] == 0: i += 1 t = 0 prev = startAt for v in arr[i:]: if v != prev: t += moveCost t += pushCost prev = v return t m, s = divmod(targetSeconds, 60) ans = min(f(m, s), f(m - 1, s + 60)) return ans

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next problem