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.
In this approach, we start from the given number and systematically try to find the smallest zero-free number whose digits' product is divisible by t. We will increment the number and check whether it satisfies the required conditions, replacing any '0' digits with '1' if they appear, since zero-free condition must be maintained.
This C implementation takes the input number as a string and repeatedly increments it until it meets the conditions of being zero-free and having a digit product divisible by t. We ensure zero-free status by replacing any '0' with '1'.
Time Complexity: O(digit count × iteration limit).
Space Complexity: O(n), where n is the length of the number string.
In this approach, we employ backtracking to generate candidate numbers meeting the requirements. By systematically building numbers through potential digits, we ensure the resulting number is zero-free and checks the product divisibility. Unlike incremental changes, this method prevents excessive retries by pruning paths failing early tests.
This Python backtracking solution recursively explores altering digits in the given number. The approach integrates pruning based on immediate product divisibility signals, constructing the smallest potential zero-free number one digit at a time.
Python
Time Complexity: Potentially exponential due to exhaustive search but pruned early.
Space Complexity: O(n), for maintaining current number and function call stack.
Go
| Approach | Complexity |
|---|---|
| Increment and Check | Time Complexity: O(digit count × iteration limit). |
| Backtracking Approach | Time Complexity: Potentially exponential due to exhaustive search but pruned early. |
| Default Approach | — |
| 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 |
3348. Smallest Divisible Digit Product II (Leetcode Hard) • Programming Live with Larry • 725 views views
Watch 1 more video solutions →Practice Smallest Divisible Digit Product II with our built-in code editor and test cases.
Practice on FleetCode