# Minimum Cost to Set Cooking Time
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/minimum-cost-to-set-cooking-time)
Canonical: https://scaleengineer.com/dsa/problems/minimum-cost-to-set-cooking-time
**Patterns:** [Math](https://scaleengineer.com/dsa/patterns/math), [Enumeration](https://scaleengineer.com/dsa/patterns/enumeration)
**Companies:** [GE Digital](https://scaleengineer.com/companies/ge-digital)
---
## Problem
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:**

![](https://assets.glich.co/dsa/minimum-cost-to-set-cooking-time/image0.png) 

**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:**

![](https://assets.glich.co/dsa/minimum-cost-to-set-cooking-time/image1.png) 

**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 <= 105`
* `1 <= targetSeconds <= 6039`

# Approaches
## Brute-Force All Possible Inputs
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.
**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.
**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`.
### Explanation
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.
### 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`.

## Iterate Through Valid Time Combinations
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.
**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.
**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.
### Explanation
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.

```java
class Solution {
    public int minCostToSetTime(int startAt, int moveCost, int pushCost, int targetSeconds) {
        long minCost = Long.MAX_VALUE;
        
        // Iterate through all possible minutes from 0 to 99
        for (int minutes = 0; minutes <= 99; minutes++) {
            int seconds = targetSeconds - minutes * 60;
            
            // Check if the calculated seconds are valid (0-99)
            if (seconds >= 0 && seconds <= 99) {
                // Construct the string to be typed.
                String timeStr;
                if (minutes == 0) {
                    timeStr = Integer.toString(seconds);
                } else {
                    timeStr = Integer.toString(minutes) + String.format("%02d", seconds);
                }
                
                minCost = Math.min(minCost, calculateCost(timeStr, startAt, moveCost, pushCost));
            }
        }
        return (int) minCost;
    }

    private long calculateCost(String s, int startAt, int moveCost, int pushCost) {
        long cost = 0;
        int currentPos = startAt;
        for (char c : s.toCharArray()) {
            int digit = c - '0';
            if (digit != currentPos) {
                cost += moveCost;
                currentPos = digit;
            }
            cost += pushCost;
        }
        return cost;
    }
}
```
### 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`.

# Solutions
### Java

```java
class Solution {
public
  int minCostSetTime(int startAt, int moveCost, int pushCost,
                     int targetSeconds) {
    int m = targetSeconds / 60;
    int s = targetSeconds % 60;
    return Math.min(f(m, s, startAt, moveCost, pushCost),
                    f(m - 1, s + 60, startAt, moveCost, pushCost));
  }
private
  int f(int m, int s, int prev, int moveCost, int pushCost) {
    if (m < 0 || m > 99 || s < 0 || s > 99) {
      return Integer.MAX_VALUE;
    }
    int[] arr = new int[]{m / 10, m % 10, s / 10, s % 10};
    int i = 0;
    for (; i < 4 && arr[i] == 0; ++i)
      ;
    int t = 0;
    for (; i < 4; ++i) {
      if (arr[i] != prev) {
        t += moveCost;
      }
      t += pushCost;
      prev = arr[i];
    }
    return t;
  }
}

```

### CPP

```cpp
class Solution {
public:
  int minCostSetTime(int startAt, int moveCost, int pushCost,
                     int targetSeconds) {
    int m = targetSeconds / 60, s = targetSeconds % 60;
    return min(f(m, s, startAt, moveCost, pushCost),
               f(m - 1, s + 60, startAt, moveCost, pushCost));
  }
  int f(int m, int s, int prev, int moveCost, int pushCost) {
    if (m < 0 || m > 99 || s < 0 || s > 99)
      return INT_MAX;
    vector<int> arr = {m / 10, m % 10, s / 10, s % 10};
    int i = 0;
    for (; i < 4 && arr[i] == 0; ++i)
      ;
    int t = 0;
    for (; i < 4; ++i) {
      if (arr[i] != prev)
        t += moveCost;
      t += pushCost;
      prev = arr[i];
    }
    return t;
  }
};

```

### Python

```python
class Solution:
    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

```