Minimum Cost to Set Cooking Time — Medium Problem & Solution

The office microwave takes a cooking time typed as at most four digits.

Difficulty: Medium
Topics: Math, Enumeration
Asked at: Amazon, Google
Time limit: 2 s
Memory limit: 256 MB
Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby

Problem statement

The office microwave takes a cooking time typed as at most four digits. It pads what you typed with leading zeros to exactly four digits, reads the first two as minutes and the last two as seconds, and cooks for minutes · 60 + seconds seconds. Seconds may go up to 99, so 0190 (1 minute 90 seconds) is 150 seconds, the same as 0230.

Your finger starts on the digit startAt. Moving it to a different digit costs moveCost; pressing the digit under it costs pushCost. Pressing the same digit twice in a row needs no move.

Return the minimum cost to make the microwave cook for exactly targetSeconds seconds.

Example 1

Input: startAt = 1, moveCost = 3, pushCost = 1, targetSeconds = 125
Output: 9
Explanation: Type `165` (1 minute 65 seconds): press 1 (1), move to 6 and press (4), move to 5 and press (4).

Example 2

Input: startAt = 1, moveCost = 2, pushCost = 1, targetSeconds = 600
Output: 6
Explanation: Type `1000` (10 minutes 0 seconds): press 1 (1), move to 0 and press (3), press 0 twice (2). The other encoding `960` costs 9.

Example 3

Input: startAt = 0, moveCost = 1, pushCost = 2, targetSeconds = 76
Output: 6
Explanation: Type `76`: move to 7, press, move to 6, press.

Constraints

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

How to solve Minimum Cost to Set Cooking Time

Only two encodings of the target are possible: the normal one, and the one that borrows a minute as 60 extra seconds (when seconds would still be at most 99). Price each typed without leading zeros and take the cheaper.

Approach

For m from 0 to 99, let s = targetSeconds - 60m; skip it unless 0 <= s <= 99.
Form the number 100m + s and take its decimal digits (no leading zeros).
Walk the digits from startAt: add moveCost when the digit differs from the finger's current digit, then always add pushCost.
Return the smallest total.

Why it works

Every four-digit display MMSS with MM · 60 + SS = target and SS <= 99 is covered by the loop. Typing extra leading zeros only adds presses: it can save no move, because going from the finger to 0 and then to the first real digit costs at least as much as going there directly.

Complexity

Time — O(1) — at most 100 candidates of 4 digits
Space — O(1)

Pitfalls

Seconds may exceed 59 — 1:90 is a valid way to enter 150 seconds and may be cheaper.
Minutes cannot exceed 99, so large targets have only one encoding.
Charge moveCost only when the next digit differs from the finger's current digit.

Reference solution

Python

def minCostSetTime(startAt: int, moveCost: int, pushCost: int, targetSeconds: int) -> int:
    best = None
    for m in range(100):
        s = targetSeconds - 60 * m
        if s < 0 or s > 99:
            continue
        cur = startAt
        cost = 0
        for ch in str(100 * m + s):
            d = ord(ch) - 48
            if d != cur:
                cost += moveCost
                cur = d
            cost += pushCost
        if best is None or cost < best:
            best = cost
    return best

JavaScript

var minCostSetTime = function(startAt, moveCost, pushCost, targetSeconds) {
    var best = Infinity;
    for (var m = 0; m <= 99; m++) {
        var s = targetSeconds - 60 * m;
        if (s < 0 || s > 99) continue;
        var digits = String(100 * m + s);
        var cur = startAt, cost = 0;
        for (var i = 0; i < digits.length; i++) {
            var d = digits.charCodeAt(i) - 48;
            if (d !== cur) { cost += moveCost; cur = d; }
            cost += pushCost;
        }
        if (cost < best) best = cost;
    }
    return best;
};

Also on the editorial tab: C, C#, C++, Go, Java, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 307 math problems · the whole catalogue