Smallest Divisible Digit Product II

Start by checking if num itself satisfies the zero-free and divisible conditions. If not, use backtracking with pruning to explore digit sequences, ensuring all partial products remain divisible by t factors. The method focuses on multiplying only by digits 1-9 and incrementally constructing candidates to quickly discard impossible paths, guaranteeing the smallest valid number is found or returning -1 if none exist.

Problem Statement

Given a string num representing a positive integer and an integer t, determine 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".

A zero-free number contains no digit 0. You must construct this number as a string and ensure that the product of all its digits modulo t is zero, using a strategy that efficiently avoids invalid sequences and leverages backtracking with pruning.

Examples

Example 1

Input: num = "1234", t = 256

Output: "1488"

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"

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"

No number greater than 11111 has the product of its digits divisible by 26.

Constraints

• 2 <= num.length <= 2 * 105
• num consists only of digits in the range ['0', '9'].
• num does not contain leading zeros.
• 1 <= t <= 1014

Solution Approach

Prime Factor Decomposition

Decompose t into its prime factors 2, 3, 5, and 7. Only these factors affect divisibility, and you can track how partial products accumulate factors to prune impossible digit combinations early.

Backtracking with Pruning

Build candidate numbers digit by digit starting from the most significant digit. Skip any digit that introduces a zero or breaks divisibility constraints. If the remaining digits cannot satisfy the remaining factor requirement, backtrack immediately.

Greedy Construction for Minimality

When multiple digits are feasible, always choose the smallest digit that maintains divisibility and zero-free conditions. This guarantees that the first valid number found is the smallest possible solution without exhaustive enumeration.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

Time complexity depends on the number of valid partial products explored; pruning reduces unnecessary branches but in worst cases may approach O(9^n). Space complexity is proportional to recursion depth, O(n), where n is the length of num.

What Interviewers Usually Probe

• Ask about how to efficiently handle large t values with only small prime factors.
• Expect discussion on pruning invalid branches early to avoid combinatorial explosion.
• Listen for awareness of constructing minimal numbers greedily within backtracking.

Common Pitfalls or Variants

Common pitfalls

• Failing to handle zeros correctly and including them in candidate numbers.
• Not pruning branches that cannot meet factor requirements, causing timeouts.
• Incorrectly assuming digits beyond 7 do not affect factor accumulation.

Follow-up variants

• Return the largest zero-free number less than or equal to num divisible by t.
• Allow zeros but require the product to ignore them in divisibility checks.
• Compute the sum of digits divisible by t instead of the product, still using backtracking.

FAQ

What is Smallest Divisible Digit Product II about?

It asks for the smallest zero-free number greater than or equal to num whose digits multiply to a product divisible by t.

Which backtracking strategy works best?

Use backtracking with pruning, selecting digits 1-9 and skipping paths where remaining digits cannot satisfy t's prime factors.

Can t have prime factors other than 2,3,5,7?

No, only 2, 3, 5, and 7 are relevant because higher primes cannot be produced by digit products 1-9.

How do I handle large num lengths?

Prune aggressively using factor tracking and skip digits that introduce zero or impossible divisibility early in recursion.

What if no number satisfies the condition?

Return -1, as the backtracking search will exhaust all feasible candidates without finding a solution.