Watch 2 video solutions for Smallest Divisible Digit Product II, a hard level problem involving Math, String, Backtracking. This walkthrough by Programming Live with Larry has 725 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
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".
Example 1:
Input: num = "1234", t = 256
Output: "1488"
Explanation:
The smallest zero-free number that is greater than 1234 and has the product of its digits divisible by 256 is 1488, with the product of its digits equal to 256.
Example 2:
Input: num = "12355", t = 50
Output: "12355"
Explanation:
12355 is already zero-free and has the product of its digits divisible by 50, with the product of its digits equal to 150.
Example 3:
Input: num = "11111", t = 26
Output: "-1"
Explanation:
No number greater than 11111 has the product of its digits divisible by 26.
Constraints:
2 <= num.length <= 2 * 105num consists only of digits in the range ['0', '9'].num does not contain leading zeros.1 <= t <= 1014Problem Overview: Given a numeric string and a target value t, you must construct the smallest number greater than or equal to the input such that the product of its digits is divisible by t. The number must be built using digits 0–9 while preserving the smallest possible lexicographic value.
Approach 1: Increment and Check (Brute Force) (Time: O(k * d), Space: O(1))
The straightforward method repeatedly increments the current number and checks whether the product of its digits is divisible by t. Convert the number to digits, multiply them, and verify product % t == 0. This approach works because every candidate is tested directly. However, when the input length grows, the number of increments can explode, especially if the valid answer is far away. The digit product calculation costs O(d) per check where d is the number of digits, making the method impractical for large constraints. Still, it provides a correctness baseline and helps validate optimized solutions.
Approach 2: Backtracking with Greedy Digit Construction (Time: O(9^d) worst case, heavily pruned; Space: O(d))
A more practical strategy builds the result digit by digit using backtracking. First factorize t using number theory insights and track what prime factors the final digit product must contain. While constructing the number, try digits from smallest to largest to keep the result minimal. Each chosen digit contributes factors to the cumulative product. If the remaining positions cannot satisfy the remaining factor requirements, prune the branch immediately. This pruning drastically reduces the search space. The algorithm effectively combines greedy ordering with recursive exploration so that the first valid completion is already the smallest valid number.
The implementation usually processes the number as a string, allowing easy digit replacement and prefix comparison with the original input. Once a prefix exceeds the original number, the remaining digits can be filled greedily with the smallest digits that satisfy the remaining factor constraints.
Recommended for interviews: Start by explaining the increment-and-check baseline to demonstrate problem understanding. Then move to the backtracking + factor tracking approach. Interviewers expect you to reduce the brute-force search space using pruning, greedy ordering, and factor decomposition.
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Increment and Check | O(k * d) | O(1) | Baseline or brute-force validation when constraints are very small |
| Backtracking with Greedy Digit Selection | O(9^d) worst case with strong pruning | O(d) | General solution for large inputs where pruning based on remaining factors drastically reduces search |