LeetCode 3348 - Smallest Divisible Digit Product II

LeetCode Problem 3348

Difficulty: 🔴 Hard
Topics: Math, String, Backtracking, Greedy, Number Theory

Solution

Problem Understanding

The problem asks us to find the smallest number that satisfies several constraints relative to a given number num and a target integer t. The input num is a string representing a positive integer, and the number must be zero-free, meaning none of its digits are zero. Additionally, the product of its digits must be divisible by t. The output is a string representing the smallest number that meets these criteria and is greater than or equal to num. If no such number exists, the function should return "-1".

The constraints indicate that num can be very long, up to 200,000 digits, which immediately rules out naive brute-force approaches that iterate through each number from num upwards. The value of t can also be large, up to 10^14, so we must consider number theory and prime factorization rather than trying to compute the product of digits for each candidate number directly.

Important edge cases include numbers containing zeros, numbers that already satisfy the product divisibility, and numbers for which no solution exists because no combination of zero-free digits can produce a product divisible by t.

Approaches

The brute-force approach would be to incrementally check each number starting from num, compute the product of its digits, and check divisibility by t. This guarantees correctness but is computationally infeasible due to the size of num and potential exponential growth of the product of digits. Additionally, iterating through numbers of length 200,000 is impossible in practice.

The optimal approach leverages number theory and greedy backtracking. First, factorize t into primes 2, 3, 5, and 7, because all digits 1-9 can be represented as a product of these primes. Then, treat the problem as filling the digits of the result such that their prime factorizations satisfy t's factorization. Use backtracking with pruning: try to match the required product while keeping the number as small as possible. If a digit cannot satisfy the remaining prime factors, increment the previous digit and restart the process. This method is feasible even for large num strings because it works digit by digit instead of iterating over full integers.

Algorithm Walkthrough

1. Factorize t into powers of 2, 3, 5, and 7. These are the only primes relevant because all digits 1-9 can be expressed as products of these primes. If t contains primes > 7, return "-1" immediately since no zero-free number can satisfy the divisibility.
2. Define a recursive or iterative function to construct the minimal number digit by digit. Start from the most significant digit of num to ensure the result is greater than or equal to num.
3. For each digit position, iterate digits 1-9 (avoiding 0) in ascending order to keep the number small. For the current digit, update the remaining prime factor requirements by subtracting the digit’s prime factor contribution.
4. If the remaining factor requirement can be satisfied with the digits left, commit this digit and move to the next position.
5. If a digit cannot satisfy the remaining prime factor requirements or if no digit is possible, backtrack to the previous digit, increment it, and attempt to fill the remaining positions again.
6. Continue until all positions are filled. If the number meets the divisibility condition, return it. If backtracking fails completely, return "-1".

Why it works: This algorithm guarantees minimality because at each position it chooses the smallest feasible digit, while backtracking ensures that the prime factorization requirement is met. Because all digits are considered in ascending order, the first valid number generated is the smallest possible.

Python Solution

class Solution:
    def smallestNumber(self, num: str, t: int) -> str:
        from functools import lru_cache
        import math

        # Factor t into primes 2,3,5,7
        def factorize(n):
            factors = {2:0,3:0,5:0,7:0}
            for p in factors:
                while n % p == 0:
                    factors[p] += 1
                    n //= p
            if n != 1:  # contains prime > 7
                return None
            return factors

        t_factors = factorize(t)
        if t_factors is None:
            return "-1"

        # Map digits to their prime factors
        digit_factors = {
            1: {2:0,3:0,5:0,7:0},
            2: {2:1,3:0,5:0,7:0},
            3: {2:0,3:1,5:0,7:0},
            4: {2:2,3:0,5:0,7:0},
            5: {2:0,3:0,5:1,7:0},
            6: {2:1,3:1,5:0,7:0},
            7: {2:0,3:0,5:0,7:1},
            8: {2:3,3:0,5:0,7:0},
            9: {2:0,3:2,5:0,7:0},
        }

        n = len(num)
        res = None

        @lru_cache(None)
        def dfs(pos, tight, f2, f3, f5, f7):
            if pos == n:
                if f2 <= 0 and f3 <= 0 and f5 <= 0 and f7 <= 0:
                    return ""
                return None
            start = int(num[pos]) if tight else 1
            for d in range(start, 10):
                if d == 0:
                    continue
                nf2 = f2 - digit_factors[d][2]
                nf3 = f3 - digit_factors[d][3]
                nf5 = f5 - digit_factors[d][5]
                nf7 = f7 - digit_factors[d][7]
                next_tight = tight and (d == int(num[pos]))
                suffix = dfs(pos+1, next_tight, nf2, nf3, nf5, nf7)
                if suffix is not None:
                    return str(d) + suffix
            return None

        result = dfs(0, True, t_factors[2], t_factors[3], t_factors[5], t_factors[7])
        return result if result else "-1"

The Python solution first factorizes t and maps each digit to its prime factor contributions. It uses memoized recursion to construct the smallest number digit by digit while subtracting used prime factors. The recursion ensures minimality and divisibility. Zeros are skipped to satisfy the zero-free constraint.

Go Solution

import (
    "math/big"
    "strconv"
)

func smallestNumber(num string, t int64) string {
    type Factors struct{ F2, F3, F5, F7 int }
    factorize := func(n int64) *Factors {
        f := &Factors{}
        for n%2 == 0 { f.F2++; n/=2 }
        for n%3 == 0 { f.F3++; n/=3 }
        for n%5 == 0 { f.F5++; n/=5 }
        for n%7 == 0 { f.F7++; n/=7 }
        if n != 1 { return nil }
        return f
    }

    tFactors := factorize(t)
    if tFactors == nil { return "-1" }

    digitFactors := map[int]Factors{
        1:{0,0,0,0}, 2:{1,0,0,0}, 3:{0,1,0,0}, 4:{2,0,0,0},
        5:{0,0,1,0}, 6:{1,1,0,0}, 7:{0,0,0,1}, 8:{3,0,0,0}, 9:{0,2,0,0},
    }

    n := len(num)
    memo := map[string]string{}

    var dfs func(pos int, tight bool, f Factors) string
    dfs = func(pos int, tight bool, f Factors) string {
        if pos == n {
            if f.F2 <= 0 && f.F3 <= 0 && f.F5 <= 0 && f.F7 <= 0 {
                return ""
            }
            return ""
        }
        key := strconv.Itoa(pos) + "_" + strconv.Itoa(btoi(tight)) + "_" +
            strconv.Itoa(f.F2)+"_"+strconv.Itoa(f.F3)+"_"+strconv.Itoa(f.F5)+"_"+strconv.Itoa(f.F7)
        if val, ok := memo[key]; ok { return val }
        start := 1
        if tight { start = int(num[pos]-'0') }
        for d := start; d <= 9; d++ {
            nf := Factors{f.F2-digitFactors[d].F2, f.F3-digitFactors[d].F3, f.F5-digitFactors