0472HardMathString

Nearest Mirror Reading on the Counter

Tracked in this browser only

Trains the technique from

This is an original problem, written from a brief that listed the technique, the difficulty, the topics, the function shape and the input bounds — none of that problem's wording, examples, hints or editorials. The link is there so you can map your practice onto the standard set.

Same function shape, different story and different numbers.

A mechanical counter on a bottling line shows a whole number as the decimal string reading, with no leading zeros. The line's engineer likes a mirror reading: one whose digits are the same read left to right as right to left.

Find the mirror reading closest to reading, where closeness is the plain difference between the two numbers and the current reading itself does not count even when it already mirrors itself. When one mirror reading sits the same distance below as another sits above, take the smaller of the two.

Return the answer as a decimal string with no leading zeros. "0" counts as a mirror reading and is a possible answer.

Examples

Example 1

Input: reading = "88"
Output: "77"

77 lies 11 below the counter and 99 lies 11 above it, so the equal-distance rule picks 77.

Example 2

Input: reading = "6000"
Output: "5995"

5995 is 5 below the counter while 6006 is 6 above it, so 5995 is the answer.

Example 3

Input: reading = "5445"
Output: "5335"

The counter already mirrors itself but is barred from being its own answer. Both 5335 and 5555 sit 110 away, and the smaller one is taken.

Constraints

1 <= reading.length <= 18
reading consists of digits only.
reading has no leading zeros.
reading represents a whole number in the range [1, 10^18 - 1].
The returned string must have no leading zeros; "0" is permitted.

The signature

The editor is preloaded with this. It matches the parent problem's shape, so a solution that works here transfers to a judge unchanged.

Python

def nearest_mirror(reading: str) -> str:

Java

public String nearestMirror(String reading)

The intended approach

Time O(d) for a counter of d digitsSpace O(d) for the handful of candidate strings

A mirror reading of the same digit count is fixed entirely by its front half, so take the front half of the counter and also the two front halves either side of it, and fold each one back on itself, dropping the middle digit on the fold when the digit count is odd. Add the two readings that change the digit count: the run of nines one digit shorter and the one-zero-one shape one digit longer. Drop the counter itself, then take the candidate with the smallest difference, preferring the smaller value when two differences match. A single-digit counter is answered directly by the digit below it.

Pythonentry point: nearest_mirror

def nearest_mirror(reading):
    # Only a handful of readings can ever be the nearest one, so build them and pick.
    # time O(d) for d digits, space O(d) for the candidate strings
    width = len(reading)
    value = int(reading)
    if width == 1:
        return str(value - 1)
    picks = {10 ** (width - 1) - 1, 10 ** width + 1}
    head = int(reading[:(width + 1) // 2])
    for shift in (-1, 0, 1):
        front = str(head + shift)
        if width % 2 == 0:
            picks.add(int(front + front[::-1]))
        else:
            picks.add(int(front + front[:-1][::-1]))
    picks.discard(value)
    best = None
    for pick in picks:
        if pick < 0:
            continue
        if best is None:
            best = pick
            continue
        gap, kept = abs(pick - value), abs(best - value)
        if gap < kept or (gap == kept and pick < best):
            best = pick
    return str(best)

The obvious version

Step outward from the counter one unit at a time. At each step test the value below first and then the value above, returning the first that reads the same both ways; testing below first makes an equal-distance pair resolve to the smaller reading on its own.

This is not filler. It was written independently of the fast solution and the two were run against thousands of random inputs to confirm they agree — which is how the answer above is known to be right. Read it when the intended approach feels like a rabbit pulled out of a hat.

Python

def bf_nearest_mirror(reading):
    value = int(reading)

    def mirrors(x):
        text = str(x)
        return text == text[::-1]

    step = 1
    while True:
        below = value - step
        if below >= 0 and mirrors(below):
            return str(below)
        if mirrors(value + step):
            return str(value + step)
        step += 1

How this problem was checked

Reference solution executed against 14 test cases — 14 passed
3 worked examples confirmed by running the code
0 eight-word sequences shared with the parent problem's text
Agrees with an independent brute-force implementation on random inputs
Test set proven to catch deliberately broken solutions
Reviewed by a separate quality pass
Function arity matches the parent problem's

Create a free account to unlock the solution

See the step-by-step animation, the intuition, and clean code in every language — free, no credit card.

Create a free account Already have an account? Sign in