We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Minimum Cost to Set Cooking Time

Number: 2266

Difficulty: Medium

Paid? No

Companies: Google

Problem Description

Given a microwave that accepts up to four digits, when you enter digits the machine left-pads them with zeroes to form a four‐digit string. The first two digits represent minutes and the last two represent seconds, whose sum (converted into seconds) is the cooking time. You are provided with the initial digit where your finger is (startAt) and two costs: moveCost (cost to move your finger from its current digit to another digit) and pushCost (cost to press the digit). Your goal is to achieve exactly targetSeconds of cooking time with a sequence of digit presses that minimizes the total cost. Note that you may press fewer than four digits (the input is normalized by adding leading zeroes), and the cooking time is computed as minutes × 60 + seconds, even if seconds ≥ 60.

Key Insights

  • The target cooking time in seconds can be represented in terms of minutes and seconds. However, there are potentially two valid (minute, second) splits.
  • One candidate is obtained by letting minutes = targetSeconds // 60 and seconds = targetSeconds % 60.
  • A second candidate is considered by “borrowing” one minute: minutes’ = minutes - 1 and seconds’ = seconds + 60, provided minutes > 0 and seconds + 60 < 100.
  • For each candidate, remove any unnecessary leading zeroes when constructing the digit sequence since extra zeros lead to additional (and avoidable) move and push costs.
  • Simulate the cost by starting at the digit startAt. For each digit of the candidate string, if the finger is already on that digit, add pushCost; otherwise add moveCost (to move there) plus pushCost.
  • The answer is the minimum cost calculated among all valid candidate representations.

Space and Time Complexity

Time Complexity: O(1) – Only a constant number of candidate splits (at most 2) are evaluated. Space Complexity: O(1) – Uses only a fixed amount of extra space.

Solution

We first determine the possible (minute, second) splits that sum to targetSeconds. The direct split is minutes = targetSeconds // 60 and seconds = targetSeconds % 60, ensuring minutes <= 99 and seconds <= 99. Another valid split might be (minutes - 1, seconds + 60) if minutes > 0 and seconds + 60 < 100, because when digits are input, the machine simply sums the minutes part (from the first two digits) and the seconds part (from the last two digits), without enforcing that seconds < 60. For a given pair, construct the digit sequence by formatting them into four digits (with possible leading zeros) and then removing any unnecessary leading zeros. While calculating the cost, simulate the digit entry starting from startAt. For the first digit, if it is not equal to startAt, add moveCost and then pushCost; if it is the same, only add pushCost. For subsequent digits, if the next digit is the same as the current finger position, add pushCost; otherwise add moveCost before pressing the digit. Finally, return the minimum cost from all valid candidates.

Code Solutions

# Python solution
def minCostSetTime(startAt: int, moveCost: int, pushCost: int, targetSeconds: int) -> int:
    # Helper function to compute cost given a candidate digit string.
    def calculate_cost(candidate: str) -> int:
        cost = 0
        current = str(startAt)  # current finger position as a character
        for digit in candidate:
            if digit == current:
                cost += pushCost
            else:
                cost += moveCost + pushCost
                current = digit
        return cost

    # Helper function to get candidate string representation:
    # We build a 4-digit string from minutes and seconds and remove unneeded leading zeros.
    def format_candidate(minutes: int, seconds: int) -> str:
        # Check validity: minutes and seconds should not exceed 99 individually.
        if minutes > 99 or seconds > 99:
            return ""
        candidate = "{:02d}{:02d}".format(minutes, seconds)
        # Remove leading zeros but keep at least one digit.
        return candidate.lstrip("0") or "0"

    res = float('inf')

    # First candidate split:
    minutes = targetSeconds // 60
    seconds = targetSeconds % 60
    candidate = format_candidate(minutes, seconds)
    if candidate:
        res = min(res, calculate_cost(candidate))

    # Second candidate: try taking one minute and adding 60 seconds if possible.
    if minutes > 0:
        minutes2 = minutes - 1
        seconds2 = seconds + 60
        candidate = format_candidate(minutes2, seconds2)
        if candidate:
            res = min(res, calculate_cost(candidate))

    return res

# Example usage:
print(minCostSetTime(1, 2, 1, 600))  # expected output: 6
← Back to All Questions