Problem

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".

Examples

Example 1

 1
 2
 3
 4
 5
 6
 7
 8
 9
10


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

1
2
3
4
5
6
7
8
9


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

1
2
3
4
5
6
7
8


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 * 10^5
  • num consists only of digits in the range ['0', '9'].
  • num does not contain leading zeros.
  • 1 <= t <= 1014

Solution

Method 1 – Greedy Digit DP (with Backtracking for Small t)

Intuition

We need the smallest zero-free number >= num whose digit product is divisible by t. For small t, we can use digit DP with memoization. For large t, the problem is very hard in general, but for practical constraints, we can use greedy and pruning.

Approach

  1. Use digit DP: for each position, try all digits 1-9 (no zeros), and keep track of the product modulo t.
  2. If the current prefix is already greater than num, we can use the smallest digits.
  3. If not, we must match or exceed the current digit in num.
  4. If t is large, limit the search (e.g., only try to change the first few digits, then fill with 1’s).
  5. If no answer is found, return -1.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31

class Solution:
    def smallestNumber(self, num: str, t: int) -> str:
        from functools import lru_cache
        n = len(num)
        digits = [int(c) for c in num]
        @lru_cache(maxsize=None)
        def dp(i, tight, prod):
            if i == n:
                return '' if prod % t == 0 else None
            start = digits[i] if tight else 1
            for d in range(start, 10):
                if d == 0: continue
                res = dp(i+1, tight and d == digits[i], (prod * d) % t)
                if res is not None:
                    return str(d) + res
            return None
        ans = dp(0, True, 1)
        if ans is not None:
            return ans
        # Try to increase the number by changing the first non-9 digit
        for i in range(n-1, -1, -1):
            if num[i] != '9' and num[i] != '0':
                prefix = num[:i] + str(int(num[i])+1)
                suffix = '1' * (n-i-1)
                candidate = prefix + suffix
                prod = 1
                for c in candidate:
                    prod *= int(c)
                if prod % t == 0:
                    return candidate
        return "-1"
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42

// Java solution is not practical for large t, but for small t, use digit DP with memoization.
import java.util.*;
class Solution {
    public String smallestNumber(String num, int t) {
        int n = num.length();
        int[] digits = new int[n];
        for (int i = 0; i < n; ++i) digits[i] = num.charAt(i) - '0';
        Map<String, String> memo = new HashMap<>();
        String res = dp(0, true, 1, digits, t, memo);
        if (res != null) return res;
        // Greedy fallback: try to increment the first non-9 digit
        for (int i = n-1; i >= 0; --i) {
            if (digits[i] != 9 && digits[i] != 0) {
                StringBuilder sb = new StringBuilder();
                for (int j = 0; j < i; ++j) sb.append(digits[j]);
                sb.append(digits[i]+1);
                for (int j = i+1; j < n; ++j) sb.append('1');
                String candidate = sb.toString();
                long prod = 1;
                for (char c : candidate.toCharArray()) prod *= c - '0';
                if (prod % t == 0) return candidate;
            }
        }
        return "-1";
    }
    private String dp(int i, boolean tight, int prod, int[] digits, int t, Map<String, String> memo) {
        if (i == digits.length) return prod % t == 0 ? "" : null;
        String key = i+","+tight+","+prod;
        if (memo.containsKey(key)) return memo.get(key);
        int start = tight ? digits[i] : 1;
        for (int d = start; d <= 9; ++d) {
            if (d == 0) continue;
            String res = dp(i+1, tight && d == digits[i], (prod * d) % t, digits, t, memo);
            if (res != null) {
                memo.put(key, d + res);
                return d + res;
            }
        }
        memo.put(key, null);
        return null;
    }
}

Complexity

  • ⏰ Time complexity: O(n * t) for small t (digit DP), but can be exponential for large t.
  • 🧺 Space complexity: O(n * t) for memoization.