Practice Smallest Divisible Digit Product II
Read the task, work through the examples, and check your approach against the constraints. Use the original LeetCode task for coding and submissions.
Smallest Divisible Digit Product II
Problem Statement
You are given a string num which represents a positive integer, and an integer t. A number is called zero-free if none of its digits are 0. Return a string representing the smallest zero-free number greater than or equal to num such that the product of its digits is divisible by t. If no such number exists, return "-1".
Source: Smallest Divisible Digit Product II on LeetCode. Use the original task for its coding environment and submissions.
Examples
# Example 1
num = "1234", t = 256
"1488"
# Example 2
num = "12355", t = 50
"12355"
# Example 3
num = "11111", t = 26
"-1"
Constraints
How to solve Smallest Divisible Digit Product II
Original notes for interview preparation, written for this problem. Reviewed .
Key insight
A digit product only contains the primes 2, 3, 5, and 7, so t must factor over them or the answer is -1. Otherwise the smallest valid number keeps the longest possible prefix of num, raises one digit, and fills the rest with as many 1s as possible followed by the fewest digits that supply the missing prime factors.
Why brute force is not enough
Counting upward from num and testing each candidate is hopeless: num has up to 2 times 10^5 digits, the gap to the answer can be astronomically large, and the digit products overflow any machine integer.
Approach
- Factor t into exponents of 2, 3, 5, and 7; if anything else remains, return -1. Track exponent vectors throughout and never form products.
- If num has no zero digit and its digits already cover the required exponents, return num unchanged.
- Write a helper that turns a required exponent vector into the fewest digits covering it: 7s and 5s as needed, a 9 per pair of 3s, an 8 per triple of 2s, then a 6 from a leftover 3 and 2, a 4 from two leftover 2s, and any single leftover 2 or 3. Sorted ascending and preceded by 1s, these form the smallest digit string of a given length with that product.
- Scan positions from right to left, maintaining the exponents contributed by the prefix before the current position. If num contains a zero, start the scan at the first zero, since no longer prefix is usable. At each position try each digit above the current one (above 0 at the zero); subtract the prefix and chosen digit from the requirement and accept the first case where the helper's digits fit in the remaining positions.
- If no position works, the answer is longer than num: 1s followed by the helper's digits, padded to length n + 1, or the helper's digits alone if they exceed that length.
Walkthrough of Example 1
num = "1234", t = 256 → "1488"
- num is "1234" and t is 256 = 2^8. The digits supply only 2^3, so num itself fails.
- Position 3 (digit 4), prefix "123" supplying 2^1, zero free positions: raising to 8 adds 2^3 but 2^4 remains; nothing fits.
- Position 2 (digit 3), prefix "12" supplying 2^1, one free position: digit 4 leaves 2^5 needing 8 and 4; digit 8 leaves 2^4 needing 8 and 2; nothing fits in one slot.
- Position 1 (digit 2), prefix "1", two free positions: digit 3 leaves 2^8 needing three digits; digit 4 leaves 2^6, covered by 8 and 8, which fits exactly.
- The result is 1, then 4, then 88, giving "1488", the expected output.
Time and space
Time O(n) · Space O(n). n is the digit count of num; each position tries nine digits with constant-size exponent arithmetic, since t at most 10^14 has fewer than 50 prime factors, and prefix exponents plus the output are linear.
Interview pitfalls
- Skipping the prime check, so a t with a factor such as 13 yields a wrong number instead of -1.
- Ignoring zeros in num: a prefix containing a zero is never usable, and at the zero's position the replacement digit starts from 1.
- Scanning left to right and taking the first feasible change, which keeps a shorter prefix and returns a larger number.
- Building the filler from 2s and 3s instead of 9s and 8s first, which uses more digits and may not fit.
- Missing the case where the answer needs more digits than num.
Follow-up questions interviewers ask
- Why does minimizing the number of non-1 digits and sorting them ascending give the smallest fixed-length filler?
- How would you find the largest valid number at most num instead?
- What changes if zero digits were allowed but the product had to be nonzero and divisible by t?
Related LeetCode Problems
Practice more problems similar to Smallest Divisible Digit Product II.
Review your practice with PhantomCodeAI
After trying the problem yourself, use the app to discuss your approach, complexity, and edge cases.