Show problems as
Classic problem #3348HardMathStringBacktrackingGreedyNumber Theory

Smallest Divisible Digit Product II

Real-world version: Least Serial Whose Digits Carry the Factor
Tracked in this browser only
Read Smallest Divisible Digit Product II on LeetCode(opens in a new tab)

The statement here is our own: the same inputs, outputs and technique.

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 starts with this. It matches the parent problem's shape, so a solution that works here works on a standard judge unchanged.

Python
def least_serial_reaching(num: str, t: int) -> str:
Java
public String leastSerialReaching(String num, long t)

More on the same topics