1227. The Smallest Multiple the Pattern Could Be

A pattern is made of digits and the wildcard ?. Replace every ? with a digit from 0 to 9 so that the resulting number, read as a decimal numeral with leading zeros allowed, is divisible by m. Report the lexicographically smallest such string, or none if there is none.

1?3, m = 7 -> 133 since 133 = 7 * 19, and no smaller digit works ???, m = 13 -> 000 the string 000 reads as 0, which 13 divides 1?3, m = 1 -> 103 everything is divisible by 1, so take the smallest digit 9, m = 7 -> none there is nothing to decide and 9 is not a multiple of 7

The answer is a STRING, not a number, so leading zeros are kept and the length never changes. Comparing strings of the same length character by character is the same as comparing the numbers, so there is no ambiguity in what smallest means.

## What most people try first

Try all ten digits at every wildcard, over all 10^q combinations, keeping the smallest string divisible by m. Six wildcards is a million and the pattern can have 1200 of them.

Reading the whole number into an integer is the other instinct and it does not survive the constraints: 1200 digits is not a 64-bit integer, nor a 128-bit one. The number never has to be formed.

## The state

Divisibility only needs the remainder. Reading digits left to right, the number so far satisfies

value(prefix + d) = value(prefix) * 10 + d remainder(prefix + d) = (remainder(prefix) * 10 + d) mod m

so the remainder of the prefix is enough to continue, and the actual value is never needed. The state after deciding position i is therefore the pair (i, remainder), and there are at most 1201 * 20 of those.

## The reachability table, which removes the backtracking entirely

Now ask whether a given state can be finished:

can[i][r] = true when, starting at position i with remainder r, the remaining characters can be filled so the whole number is divisible by m can[n][0] = true, and can[n][r] = false for r other than 0 can[i][r] = true when some digit d allowed at position i has can[i+1][(r*10 + d) mod m] true

Filling that from the end backwards costs O(n * m * 10), which at the limits is 240000 steps. With the table in hand the search never takes a step it has to undo: a digit is only accepted when the state it leads to is known to be completable. So the forward pass is O(n * 10) and the whole program is linear in the input.

This is the pattern worth taking away. A FORWARD CHECK that is exact turns a backtracking search into a single pass. Compare #1204, where the forward check is a cheap necessary condition and the search still backtracks, with this one, where the check is necessary AND sufficient and the search never backtracks at all.

## Why the first complete string is the smallest

Positions are filled left to right, digits are tried 0 through 9 in increasing order, and every digit accepted leads to a completable state. So the first complete string is smaller at the earliest point of difference than any other, which is what smallest means for strings of equal length.

## Why the reference does not recurse

The search is one decision per position and the input can be 1200 characters long, so a recursion goes 1200 frames deep. Python's default recursion limit is 1000, and raising it does not raise the C stack that CPython actually uses, so a recursive reference crashes here. It is not only Python: a frame holding a few locals is tens of bytes, and at tens of thousands of positions the default thread stack in Java and the main stack in C run out too.

So the reference carries the stack itself. The only thing a recursive frame holds that a loop would lose is WHICH OPTION the frame was about to try next, so that is what the explicit stack stores:

``` nxt[i] = index of the next option to try at position i

i = 0; nxt[0] = 0 while i >= 0: if i == n: a complete string if accepted: answer it and stop i = i - 1 otherwise go back continue if nxt[i] has run past the options at i: i = i - 1 this position is exhausted, go back continue take option nxt[i] and increment nxt[i] <- this is the resume point if the option is refused: continue stay at i, try the next one record it; nxt[i+1] = 0; i = i + 1 descend ```

Three details make or break it. nxt[i] is incremented BEFORE the descent, so coming back to position i continues from the next option rather than repeating the one that just failed, which would loop forever. nxt[i+1] is reset to 0 on every descent, not once at the start, because position i+1 may be entered many times and each entry must start from its first option. And going back is i = i - 1 with no undo of out[i], because out[i] is overwritten before it is ever read again; the carried state lives in stv[i], indexed by position, so it unwinds for free.

## The settled boundaries

m = 1 makes everything divisible, so the answer is the pattern with every wildcard set to 0. A pattern with no wildcard is either already divisible or none. Leading zeros are explicitly allowed, which is why ??? with m = 13 answers 000 rather than the smallest three-digit multiple; that is a decision the statement has to make and does.

## Cost

O(n * m * 10) to build the table and O(n * 10) to walk it, so linear in the pattern length for fixed m.

Constraints - `1 ≤ length of the pattern ≤ 1200` - `1 ≤ m ≤ 20` - every pattern character is a digit or `?` - the value can have 1200 digits, so it must never be formed as an integer