Zero-Free Number With a Multiple Digit Product

Hard

You are given a very long positive number as a string start and an integer divisor. Call a number **zero-free** if its decimal notation contains no digit 0. Find the smallest zero-free number that is at least start and whose product of digits is divisible by divisor. Return it as a string. If no such number exists, return "-1".

Example 1

start="1500", divisor=36 → '1549'

For a number 15xy we need 5·x·y to be a multiple of 36, so x·y must be a multiple of 36; the smallest such ending is 49. The answer is 1549: 1·5·4·9 = 180 = 36 · 5.

Example 2

start="2357", divisor=10 → '2357'

2·3·5·7 = 210 is already a multiple of 10 and there are no zeros, so the number itself is the answer.

Example 3

start="99", divisor=22 → '-1'

22 = 2 · 11, and no digit contributes a factor of 11, so the answer is "-1".

Constraints

2 ≤ len(start) ≤ 2 · 10⁵
start consists of digits and does not begin with 0
1 ≤ divisor ≤ 10¹⁴

Have you seen this problem in a real interview?

Solved by0

Tried by0

Submissions0

Acceptance—

Topics

Greedy Math String Backtracking Number Theory

Similar problems

Largest Palindrome That Is a Multiple Hard Signs Between the Digits Hard Letter Sum Cipher Hard Pattern Woven Several Times Hard Heaviest Picks of Distinct Letters Hard

Input

start="1500", divisor=36

Expected

'1549'

Run checks the first 3 tests in your browser. Submit checks all 96 tests on the server, hidden ones included.