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 theminimum cost to set targetSeconds seconds of cooking time.

Remember that one minute consists of 60 seconds.

Examples

Example 1

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15


![](https://assets.leetcode.com/uploads/2021/12/30/1.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

1
2
3
4
5
6
7
8


![](https://assets.leetcode.com/uploads/2021/12/30/2.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 <= 10^5
  • 1 <= targetSeconds <= 6039

Solution

Method 1 – Enumeration of All Valid Time Representations

Intuition

To minimize the cost, we enumerate all possible ways to represent the target time in minutes and seconds (within the microwave’s constraints), then simulate the process of entering each representation and calculate the cost. We pick the representation with the lowest cost.

Approach

  1. For each possible (minutes, seconds) such that 0 <= minutes <= 99, 0 <= seconds <= 99, and 1 <= total_seconds = minutes * 60 + seconds == targetSeconds:
    • Generate the 4-digit string representation.
    • Simulate entering the digits, tracking finger movement and pushes.
    • Calculate the total cost for this representation.
  2. Return the minimum cost among all valid representations.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21

class Solution {
public:
    int minCostSetTime(int startAt, int moveCost, int pushCost, int targetSeconds) {
        int ans = INT_MAX;
        for (int m = 0; m <= 99; ++m) {
            int s = targetSeconds - m * 60;
            if (s < 0 || s > 99) continue;
            string t = to_string(m * 100 + s);
            while (t.size() < 4) t = "0" + t;
            int cur = 0, pos = startAt;
            for (char c : t) {
                int d = c - '0';
                if (pos != d) cur += moveCost;
                cur += pushCost;
                pos = d;
            }
            ans = min(ans, cur);
        }
        return ans;
    }
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17

func minCostSetTime(startAt, moveCost, pushCost, targetSeconds int) int {
    ans := 1<<31 - 1
    for m := 0; m <= 99; m++ {
        s := targetSeconds - m*60
        if s < 0 || s > 99 { continue }
        t := fmt.Sprintf("%04d", m*100+s)
        cur, pos := 0, startAt
        for i := 0; i < 4; i++ {
            d := int(t[i] - '0')
            if pos != d { cur += moveCost }
            cur += pushCost
            pos = d
        }
        if cur < ans { ans = cur }
    }
    return ans
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19

class Solution {
    public int minCostSetTime(int startAt, int moveCost, int pushCost, int targetSeconds) {
        int ans = Integer.MAX_VALUE;
        for (int m = 0; m <= 99; ++m) {
            int s = targetSeconds - m * 60;
            if (s < 0 || s > 99) continue;
            String t = String.format("%04d", m * 100 + s);
            int cur = 0, pos = startAt;
            for (char c : t.toCharArray()) {
                int d = c - '0';
                if (pos != d) cur += moveCost;
                cur += pushCost;
                pos = d;
            }
            ans = Math.min(ans, cur);
        }
        return ans;
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19

class Solution {
    fun minCostSetTime(startAt: Int, moveCost: Int, pushCost: Int, targetSeconds: Int): Int {
        var ans = Int.MAX_VALUE
        for (m in 0..99) {
            val s = targetSeconds - m * 60
            if (s < 0 || s > 99) continue
            val t = ("%04d").format(m * 100 + s)
            var cur = 0; var pos = startAt
            for (c in t) {
                val d = c - '0'
                if (pos != d) cur += moveCost
                cur += pushCost
                pos = d
            }
            ans = minOf(ans, cur)
        }
        return ans
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17

class Solution:
    def minCostSetTime(self, startAt: int, moveCost: int, pushCost: int, targetSeconds: int) -> int:
        ans = float('inf')
        for m in range(100):
            s = targetSeconds - m * 60
            if s < 0 or s > 99:
                continue
            t = f"{m*100+s:04d}"
            cur, pos = 0, startAt
            for c in t:
                d = int(c)
                if pos != d:
                    cur += moveCost
                cur += pushCost
                pos = d
            ans = min(ans, cur)
        return ans
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20

impl Solution {
    pub fn min_cost_set_time(start_at: i32, move_cost: i32, push_cost: i32, target_seconds: i32) -> i32 {
        let mut ans = i32::MAX;
        for m in 0..100 {
            let s = target_seconds - m * 60;
            if s < 0 || s > 99 { continue; }
            let t = format!("{:04}", m * 100 + s);
            let mut cur = 0;
            let mut pos = start_at;
            for c in t.chars() {
                let d = c.to_digit(10).unwrap() as i32;
                if pos != d { cur += move_cost; }
                cur += push_cost;
                pos = d;
            }
            ans = ans.min(cur);
        }
        ans
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19

class Solution {
    minCostSetTime(startAt: number, moveCost: number, pushCost: number, targetSeconds: number): number {
        let ans = Number.MAX_SAFE_INTEGER;
        for (let m = 0; m < 100; ++m) {
            const s = targetSeconds - m * 60;
            if (s < 0 || s > 99) continue;
            const t = ("0000" + (m * 100 + s)).slice(-4);
            let cur = 0, pos = startAt;
            for (const c of t) {
                const d = Number(c);
                if (pos !== d) cur += moveCost;
                cur += pushCost;
                pos = d;
            }
            ans = Math.min(ans, cur);
        }
        return ans;
    }
}

Complexity

  • ⏰ Time complexity: O(100 * 100) since we enumerate all valid minute/second pairs.
  • 🧺 Space complexity: O(1).