0508EasyMathEnumeration

Next Shelf Label

Tracked in this browser only

Trains the technique from

LeetCode 3345Smallest Divisible Digit Product I

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 stockroom numbers its shelves with positive whole numbers. A shelf label is valid for a crate of type t when the product of the label's decimal digits is a multiple of t.

The next free shelf is n, and the crate may be placed on shelf n or on any higher-numbered shelf. Return the smallest label at or above n that is valid for t.

A label containing the digit 0 has a digit product of 0, and 0 counts as a multiple of every positive t.

Examples

Example 1

Input: n = 15, t = 7
Output: 17

Shelf 15 has digit product 5 and shelf 16 has digit product 6, neither of which is a multiple of 7. Shelf 17 has digit product 7.

Example 2

Input: n = 16, t = 10
Output: 20

Shelves 16 through 19 have digit products 6, 7, 8 and 9. Shelf 20 has digit product 0, which counts as a multiple of 10.

Example 3

Input: n = 99, t = 9
Output: 99

Shelf 99 has digit product 81, and 81 is 9 times 9.

Constraints

1 <= n <= 100
1 <= t <= 10

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 smallest_shelf_label(n: int, t: int) -> int:

Java

public int smallestShelfLabel(int n, int t)

The intended approach

Time O(1): at most ten labels are examined, each with at most three digits.Space O(1).

Any label whose last digit is `0` has a digit product of `0`, which is a multiple of every `t` in range, so the first label at or above `n` that ends in `0` is always valid. That gives a hard ceiling at most nine above `n`, so walk the labels from `n` up to that ceiling, multiply the digits of each, and return the first one whose product is a multiple of `t`.

Pythonentry point: smallest_shelf_label

def smallest_shelf_label(n, t):
    # Every label ending in 0 has a digit product of 0, and 0 is a multiple of
    # every divisor allowed here, so the first such label at or above n is always
    # acceptable. That caps the search at the ten labels from n up to that one.
    # O(1) time, O(1) space.
    capped = ((n + 9) // 10) * 10
    label = n
    while label < capped:
        product = 1
        rest = label
        while rest > 0:
            product *= rest % 10
            rest //= 10
        if product % t == 0:
            return label
        label += 1
    return capped

The obvious version

Walk upward from `n` with no ceiling at all, forming each label's digit product from its decimal spelling and stopping at the first label whose product is a multiple of `t`.

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_smallest_shelf_label(n, t):
    label = n
    while True:
        product = 1
        for ch in str(label):
            product *= int(ch)
        if product % t == 0:
            return label
        label += 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