3348. Smallest Divisible Digit Product II

  • String
  • Greedy
  • Math
  • Number Theory
  • Enumeration
TIME
O(n)
SPACE
O(n)
problem on leetcode ↗source on github ↗

Intuition

Digits 1..9 only carry the prime factors 2, 3, 5, 7. So first strip those primes out of t; if anything remains, no digit product can ever be divisible by t → "-1". What's left is a required exponent tuple (a2, a3, a5, a7) that the answer's digits must jointly supply.

Two building blocks:

  1. Minimal covering multiset. Cover the required exponents with the fewest, largest digits, 9 = 3^2, 8 = 2^3, 6 = 2*3, and forced 5s / 7s (only digit 5 gives a factor 5, only 7 gives a factor 7). Sorting the multiset ascending gives the lexicographically smallest arrangement, and its size is the minimum number of "significant" digits needed.
  2. Smallest number of a given length that covers. Pad the front with 1s (they contribute nothing) and place the covering multiset at the end.

Approach

  1. Reduce t by dividing out 2, 3, 5, 7 → exponents (a2,a3,a5,a7); leftover > 1 → "-1".
  2. Same length as num:
    • If num is zero-free and its digit product already covers the exponents → return num.
    • Otherwise find the largest position i to bump: keep the (zero-free) prefix num[0..i-1], set digit i to the smallest value > num[i] such that the remaining exponents can still be covered by the suffix positions, then fill the suffix with 1s + minimal covering digits. A larger branch position always yields a smaller result, so the first feasible one (scanning right to left) wins. The valid branch range is capped at the first 0 in num (a kept prefix must stay zero-free; the 0 itself can be bumped).
  3. Fallback to a longer number: if no same-length answer exists, the answer has length L = max(n+1, mincount) and is "1" * (L - mincount) + minimalDigits the smallest zero-free covering number of that length.

Complexity

  • Time: O(n), cumulative prefix exponents, one right-to-left scan with O(1) work per position (8 candidate digits), suffix built once
  • Space: O(n), prefix arrays and the output

Edge Cases

  • t has a prime factor other than 2/3/5/7 → "-1" (Example 3)
  • num already valid → return it (Example 2)
  • num contains 0s → branch position is capped at the first 0
  • t = 1 → any zero-free number works → smallest zero-free >= num
  • Required 5s / 7s force 5 / 7 digits (e.g. 7^3 → "777")
  • Use 64-bit for t (up to 10^14); digit exponents are small ints

Code

class Solution:
    def smallestNumber(self, num: str, t: int) -> str:
        """
        3348. Smallest Divisible Digit Product II
        Time: O(n)
        Space: O(n)
        """
        # Reduce t to its 2/3/5/7 exponents; any leftover prime is impossible.
        exp = {2: 0, 3: 0, 5: 0, 7: 0}
        for p in (2, 3, 5, 7):
            while t % p == 0:
                t //= p
                exp[p] += 1
        if t != 1:
            return "-1"
        A2, A3, A5, A7 = exp[2], exp[3], exp[5], exp[7]

        # Per-digit (2,3,5,7) exponent contributions.
        C = {
            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),
        }

        def leftover(r2: int, r3: int):
            # smallest digits covering r2 twos (0..2) and r3 threes (0..1)
            if r2 == 1 and r3 == 1:
                return [6]
            if r2 == 2 and r3 == 1:
                return [2, 6]
            if r2 == 1 and r3 == 0:
                return [2]
            if r2 == 2 and r3 == 0:
                return [4]
            if r2 == 0 and r3 == 1:
                return [3]
            return []

        def build_digits(x2, x3, x5, x7):
            n9, r3 = divmod(x3, 2)
            n8, r2 = divmod(x2, 3)
            ds = [9] * n9 + [8] * n8 + leftover(r2, r3) + [5] * x5 + [7] * x7
            ds.sort()
            return ds

        def mincount(x2, x3, x5, x7):
            n9, r3 = divmod(x3, 2)
            n8, r2 = divmod(x2, 3)
            return n9 + n8 + len(leftover(r2, r3)) + x5 + x7

        S = build_digits(A2, A3, A5, A7)
        S_str = "".join(map(str, S))
        min_c = len(S)

        n = len(num)
        digs = [ord(c) - 48 for c in num]

        # First zero index (kept prefix must be zero-free).
        z = n
        for i, d in enumerate(digs):
            if d == 0:
                z = i
                break

        # Cumulative exponent contribution of num[0..i-1] (valid for i <= z).
        pref = [(0, 0, 0, 0)] * (n + 1)
        cur = (0, 0, 0, 0)
        for i in range(n):
            if i < z:
                c = C[digs[i]]
                cur = (cur[0] + c[0], cur[1] + c[1], cur[2] + c[2], cur[3] + c[3])
            pref[i + 1] = cur

        def remaining(contrib):
            return (max(0, A2 - contrib[0]), max(0, A3 - contrib[1]),
                    max(0, A5 - contrib[2]), max(0, A7 - contrib[3]))

        # Candidate: num itself (zero-free and already covers t).
        if z == n:
            f = pref[n]
            if f[0] >= A2 and f[1] >= A3 and f[2] >= A5 and f[3] >= A7:
                return num

        # Same length: bump at the largest feasible position.
        hi = z if z < n else n - 1
        for i in range(hi, -1, -1):
            base = pref[i]
            avail = n - 1 - i
            for d in range(digs[i] + 1, 10):
                cd = C[d]
                contrib = (base[0] + cd[0], base[1] + cd[1], base[2] + cd[2], base[3] + cd[3])
                r2, r3, r5, r7 = remaining(contrib)
                need = mincount(r2, r3, r5, r7)
                if need <= avail:
                    suf = build_digits(r2, r3, r5, r7)
                    suffix = "1" * (avail - need) + "".join(map(str, suf))
                    return num[:i] + str(d) + suffix

        # No same-length answer: use the smallest longer covering number.
        L = max(n + 1, min_c)
        return "1" * (L - min_c) + S_str