Largest number by changing up to k digits to 5: Frontier Interview's solution

Question: Largest number by changing up to k digits to 5

Companies: Microsoft

Difficulty: Easy

Problem statement

You are given a string s that holds a positive integer (digits only, no leading zero) and an integer k.

In one operation you pick any digit of s that is not 5 and change it to 5. You may perform at most k operations.

Implement:

def maximize_with_fives(s: str, k: int) -> str: ...

Return the largest number you can obtain, as a string.

Constraints

1 <= len(s) <= 10^5
0 <= k <= 10^5
The number may be too large for a 64-bit integer, so work with the string.

Example 1

s = "1234", k = 2
output: "5534"

Change the 1 and the 2. Changing the 3 or 4 instead gives a smaller result.

Example 2

s = "9183", k = 1
output: "9583"

The leading 9 would get smaller, so leave it. The best single change is the 1.

Part 2. Now you must use exactly k operations. Return the largest result, or report that it is impossible when s has fewer than k digits that are not 5.

Reconstructed from the reported question; details may differ from what interviewers ask.

Approach

Clarify first. The input is a string s of digits (a positive integer, no leading zero) and an integer k. One operation picks a digit that is not 5 and changes it to 5. Ask three things before coding:

At most k or exactly k? The usual version is "at most k": you may stop early. Solve that first, then handle "exactly k" (see Follow-ups and the exact flag in the code).
Return type. Return the new string. The number can have thousands of digits, so do not convert it to int.
Can k be larger than the length? Yes. Extra operations are simply unused.

Key observation. A change at one position only affects that digit, and positions are compared from the left. So:

Changing a digit d < 5 to 5 always makes the number larger.
Changing a digit d > 5 to 5 always makes it smaller. Never do it unless you are forced to.
A gain at a more significant (more left) position beats any gains to its right. Raising the digit at position i adds at least 10^(n-1-i), and all positions to the right together can add less than that.

Brute force. Try every set of at most k positions to change and keep the largest result. That is O(C(n, k) * n). It is useful only to check the greedy on small inputs.

Greedy. Scan left to right. Whenever you see a digit below 5 and you still have operations left, change it to 5 and spend one operation. Stop when k reaches 0.

Why it is optimal (exchange argument). Take any optimal set of changes. If it skips a digit below 5 at position i but changes something to its right, move that operation to i: the number gets larger, which is a contradiction. If it changes a digit above 5, drop that change: the number gets larger again. So an optimal answer changes exactly the leftmost min(k, count of digits < 5) digits that are below 5, which is what the greedy does.

Invariant. After processing position i, the prefix s[0..i] is the largest prefix you can reach with the operations spent so far, and the remaining budget is k minus the number of changes made.

Code

from __future__ import annotations


def maximize_with_fives(s: str, k: int, exact: bool = False) -> str:
    """Return the largest number reachable by changing non-5 digits of `s` to 5.

    exact=False: use at most k operations (the base problem).
    exact=True:  use exactly k operations; raises ValueError if impossible.
    """
    if not s.isdigit():
        raise ValueError("s must contain only digits")
    if k < 0:
        raise ValueError("k must be non-negative")

    digits = list(s)
    remaining = k

    # Pass 1: every change of a digit below 5 is a gain; spend them leftmost first.
    for i, ch in enumerate(digits):
        if remaining == 0:
            break
        if ch < "5":
            digits[i] = "5"
            remaining -= 1

    if not exact or remaining == 0:
        return "".join(digits)

    # Pass 2 (exact only): all digits below 5 are already 5. Remaining operations
    # must hit digits above 5, which lowers the number. Pick the rightmost ones,
    # because a loss in a less significant place costs less.
    for i in range(len(digits) - 1, -1, -1):
        if remaining == 0:
            break
        if digits[i] > "5":
            digits[i] = "5"
            remaining -= 1

    if remaining > 0:
        raise ValueError("not enough non-5 digits to use exactly k operations")
    return "".join(digits)


def _brute_force(s: str, k: int) -> str:
    """Try every subset of at most k non-5 positions (small inputs only)."""
    from itertools import combinations

    candidates = [i for i, ch in enumerate(s) if ch != "5"]
    best = s
    for size in range(1, min(k, len(candidates)) + 1):
        for chosen in combinations(candidates, size):
            t = list(s)
            for i in chosen:
                t[i] = "5"
            best = max(best, "".join(t))  # same length, so string order = numeric order
    return best


if __name__ == "__main__":
    assert maximize_with_fives("1234", 2) == "5534"
    assert maximize_with_fives("9183", 1) == "9583"
    assert maximize_with_fives("7896", 3) == "7896"
    assert maximize_with_fives("555", 4) == "555"
    assert maximize_with_fives("4", 0) == "4"
    assert maximize_with_fives("2060", 10) == "5565"
    assert maximize_with_fives("9183", 3, exact=True) == "9555"
    assert maximize_with_fives("9183", 4, exact=True) == "5555"
    assert maximize_with_fives("786", 1, exact=True) == "785"

    import random

    for _ in range(2000):
        n = random.randint(1, 6)
        s = str(random.randint(1, 9)) + "".join(random.choice("0123456789") for _ in range(n - 1))
        k = random.randint(0, 7)
        assert maximize_with_fives(s, k) == _brute_force(s, k), (s, k)
    print("all tests passed")

Complexity

Time: O(n) for n = len(s). Each pass looks at each digit at most once. The exact mode adds one more O(n) pass.
Space: O(n) for the output digit list (strings are immutable in Python). Extra working space beyond the output is O(1).
Brute force (for checking only): O(C(n, k) * n).

Test cases

s = "1234", k = 2 → "5534" (change the two leftmost low digits).
s = "9183", k = 1 → "9583" (skip the leading 9; change the 1).
s = "7896", k = 3 → "7896" (every digit is above 5; do nothing).
s = "555", k = 4 → "555" (no digit can be changed).
s = "4", k = 0 → "4" (no budget).
s = "2060", k = 10 → "5565" (budget larger than the number of useful changes; the 6 stays).
s = "1" * 100000, k = 50000 → first 50,000 digits become 5, the rest stay 1. Checks linear time and no int conversion.
Exact mode: s = "9183", k = 3, exact → "9555"; k = 4, exact → "5555"; s = "786", k = 1, exact → "785" (the forced loss goes to the rightmost digit above 5); s = "55", k = 1, exact → error.

Follow-ups

Exactly k operations. Spend operations on all digits below 5 first, left to right. If budget remains, change digits above 5 starting from the right, since the loss is smallest there. If you still have budget after every non-5 digit is changed, there is no valid answer. Same O(n).
Minimize instead of maximize. Mirror the rule: change digits above 5 to 5, leftmost first, and never touch digits below 5. If the target digit could be 0, the leading digit must be skipped so the number keeps its length.
Any target digit d, or a choice of replacement digits. With a fixed target d, the same greedy works with d in place of 5. If each operation may change a digit to any value, change the leftmost k digits that are not 9 to 9 (with the leading digit kept non-zero for the minimize variant).
Insert a 5 instead of replacing (a common Microsoft variant). For a positive number, insert 5 before the first digit smaller than 5. For a negative number, insert it before the first digit larger than 5. If there is no such digit, append at the end. O(n).
Swaps instead of replacements. "At most one swap" (largest number) is solved by recording the last index of each digit and swapping the first digit that has a larger digit later. "At most k swaps" needs backtracking: at each position, try swapping in the largest digit to its right, branch on ties, and prune. Worst case is exponential, so discuss bounds with the interviewer.

Interviewer expectations

Mid-level (L4)

Notices that digits above 5 must never be changed and digits below 5 should be changed from the left.
Writes a correct one-pass solution on a string, without converting to int.
Handles k = 0, all 5s, and k larger than the useful changes.

Senior (L5)

Asks "at most or exactly k" up front and solves both.
Gives a clear exchange argument for why left-to-right is optimal.
Writes a small brute force or randomized check to back up the greedy.

Staff (L6+)

Places this in the family of digit-greedy problems (replace, insert, remove, swap) and explains why replace is greedy-safe but k swaps is not.
Discusses very large inputs: streaming the digits, the answer as a prefix of changes, and returning only the changed positions when that is cheaper.
Keeps the code short and the API explicit about the failure case for exact mode.