0836HardMathStringBacktrackingGreedyNumber Theory

Least Serial Whose Digits Carry the Factor

Tracked in this browser only

Trains the technique from

LeetCode 3348Smallest Divisible Digit Product II

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 press stamps serial numbers. num is the serial it is about to stamp, written as a string of digits with no leading zero.

The digit product of a serial is what you get by multiplying all of its digits together. A serial is acceptable when it carries no digit 0 and its digit product is a multiple of t.

Return the smallest acceptable serial that is greater than or equal to num, as a string. The answer may hold more digits than num. If no acceptable serial exists at all, return the string "-1".

Examples

Example 1

Input: num = "15", t = 6
Output: "16"

The serial "16" carries no zero and its digit product is 6, which is a multiple of 6. No acceptable serial lies between 15 and 16.

Example 2

Input: num = "99", t = 11
Output: "-1"

A digit product is a product of single digits, so it can never carry the factor 11, and the answer is the string "-1".

Example 3

Input: num = "99", t = 49
Output: "177"

The factor 49 needs two sevens, and no two-digit serial at or above 99 supplies them, so the answer grows to three digits: "177" has digit product 49.

Constraints

2 <= num.length <= 200000
num consists of digits only
num has no leading zero
1 <= t <= 100000000000000

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 least_serial_reaching(num: str, t: int) -> str:

Java

public String leastSerialReaching(String num, long t)

The intended approach

Time O(L * 9 * D) for a serial of L digits, where D is the small work of the coverage test.Space O(L) for the running prefix contributions.

A digit product multiplies one-digit numbers, so it can only ever carry the primes two, three, five and seven. Strip those from the target; anything left over means no serial can work at all. What remains is a demand for so many of each of those four primes. The key sub-question is how few digits can supply a given demand: a five comes only from the digit 5 and a seven only from the digit 7, and neither carries anything else, so each takes a slot of its own, while the twos and threes are covered by slots giving three twos, two threes, or one of each. With that test in hand, keep the longest prefix of the serial that still leaves the rest coverable, raise the next digit as little as possible, then fill the remaining slots with the smallest digit at each step that keeps the rest coverable. If no serial of the same width works, take the fewest digits that can and open with a one.

Pythonentry point: least_serial_reaching

def least_serial_reaching(num, t):
    # only 2s, 3s, 5s and 7s contribute, so the target must reduce to those primes
    need = {2: 0, 3: 0, 5: 0, 7: 0}
    left = t
    for prime in (2, 3, 5, 7):
        while left % prime == 0:
            left //= prime
            need[prime] += 1
    if left != 1:
        return "-1"

    width = len(num)
    digits = [int(ch) for ch in num]

    def contributes(digit):
        share = {2: 0, 3: 0, 5: 0, 7: 0}
        left = digit
        for prime in (2, 3, 5, 7):
            while left % prime == 0:
                left //= prime
                share[prime] += 1
        return share

    SHARE = [None] + [contributes(d) for d in range(1, 10)]

    def slots_needed(short):
        """Fewest digits that can supply this shortfall.

        A five can only come from the digit 5 and a seven only from the digit 7,
        and neither digit carries anything else, so each of those needs a slot of
        its own. The rest is covered by digits drawn from 1, 2, 3, 4, 6, 8, 9,
        where the only slots worth using give three twos, two threes, or one of
        each, so try each count of the mixed kind.
        """
        base = short[5] + short[7]
        a = short[2]
        b = short[3]
        best = None
        for mixed in range(0, min(a, b) + 1):
            need = mixed + (a - mixed + 2) // 3 + (b - mixed + 1) // 2
            if best is None or need < best:
                best = need
        return base + (0 if best is None else best)

    def reachable(short, slots):
        return slots_needed(short) <= slots

    def fill(short, slots):
        """Smallest digit string of exactly `slots` digits covering `short`."""
        out = []
        for _ in range(slots):
            for digit in range(1, 10):
                share = SHARE[digit]
                rest = {p: max(0, short[p] - share[p]) for p in (2, 3, 5, 7)}
                if reachable(rest, slots - len(out) - 1):
                    out.append(str(digit))
                    short = rest
                    break
        return "".join(out)

    # keep as long a prefix of num as possible, then raise one digit
    prefix = [{2: 0, 3: 0, 5: 0, 7: 0}]
    for d in digits:
        run = dict(prefix[-1])
        if d != 0:
            for p in (2, 3, 5, 7):
                run[p] += SHARE[d][p]
        else:
            run = None
        prefix.append(run)
        if run is None:
            break

    # try the longest prefix first
    for keep in range(len(prefix) - 1, -1, -1):
        if prefix[keep] is None:
            continue
        if keep == width:
            short = {p: max(0, need[p] - prefix[keep][p]) for p in (2, 3, 5, 7)}
            if all(v == 0 for v in short.values()):
                return num
            continue
        base = prefix[keep]
        for raise_to in range(digits[keep] + 1, 10):
            share = SHARE[raise_to]
            run = {p: base[p] + share[p] for p in (2, 3, 5, 7)}
            short = {p: max(0, need[p] - run[p]) for p in (2, 3, 5, 7)}
            slots = width - keep - 1
            if reachable(short, slots):
                return num[:keep] + str(raise_to) + fill(short, slots)

    # nothing of the same width works, so the answer is one digit longer, or
    # longer still if the demand cannot fit in that many digits
    grown = width + 1
    room = slots_needed(need)
    if room > grown:
        grown = room
    return fill(dict(need), grown)

The obvious version

Count upwards from the serial, skipping anything holding a zero digit, and return the first value whose digit product is a multiple of the target. If nothing of that width works, scan the next width from its smallest value. Only usable on short serials, but it assumes nothing about prime factors.

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_least_serial_reaching(num, t):
    width = len(num)
    start = int(num)

    def product(text):
        out = 1
        for ch in text:
            out *= int(ch)
        return out

    limit = 10 ** width
    value = start
    while value < limit:
        text = str(value)
        if "0" not in text and product(text) % t == 0:
            return text
        value += 1
    # widen by one digit and scan from the smallest
    value = 10 ** width
    while value < 10 ** (width + 2):
        text = str(value)
        if "0" not in text and product(text) % t == 0:
            return text
        value += 1
    return "-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