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 <= 1014In 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'.
C++
Java
Python
C#
JavaScript
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.
Time Complexity: Potentially exponential due to exhaustive search but pruned early.
Space Complexity: O(n), for maintaining current number and function call stack.
| 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. |
How many LeetCode problems should you solve? #leetcode #techinterview #developer #softwareengineer • CrioDo • 304,699 views views
Watch 9 more video solutions →Practice Smallest Divisible Digit Product II with our built-in code editor and test cases.
Practice on FleetCode