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 <= 1014#3348 Smallest Divisible Digit Product II asks you to construct the lexicographically smallest number (often treated as a string) whose digit product satisfies a given divisibility constraint. Because digit multiplication grows quickly and the number itself can become large, the problem is typically handled using number theory and digit construction rather than brute-force enumeration.
A common strategy is to factorize the target divisor and determine how digits (1–9) contribute prime factors such as 2, 3, 5, and 7. Using these factors, you can greedily or recursively build the smallest valid number while ensuring the remaining factor requirements can still be satisfied. Many solutions treat the number as a string and use backtracking with pruning or a greedy reconstruction to minimize digits while meeting the factor constraints.
Careful pruning is essential: if remaining positions cannot supply the required factors, that branch is abandoned. The overall search is limited by digit choices and factor feasibility checks. Typical implementations run in roughly O(10^d) worst-case search with heavy pruning and use O(d) auxiliary space for recursion or construction.
| Approach | Time Complexity | Space Complexity |
|---|---|---|
| Greedy with factor decomposition | O(d * 9) | O(d) |
| Backtracking with pruning | O(10^d) worst case (pruned heavily in practice) | O(d) |
CrioDo
Use these hints if you're stuck. Try solving on your own first.
<code>t</code> should only have 2, 3, 5 and 7 as prime factors.
Find the shortest suffix that must be changed.
Try to form the string greedily.
Watch expert explanations and walkthroughs
Jot down your thoughts, approach, and key learnings
Problems combining digit construction, greedy reasoning, and number theory appear in many top tech interviews. While the exact problem may vary, similar patterns involving factorization and constrained number building are common.
Most solutions treat the number as a string or dynamic digit array since the resulting value may be very large. Additional structures like maps or arrays are used to track remaining prime factor requirements during construction.
The optimal approach typically combines number theory and greedy digit construction. By factorizing the required divisor and mapping those factors to digits 1–9, you can construct the smallest valid number while ensuring the remaining digits can still satisfy the factor requirements.
The difficulty comes from balancing lexicographical minimization with multiplicative constraints. You must carefully track prime factors of the product and prune invalid branches while constructing the smallest possible number.