We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Smallest Divisible Digit Product II

Number: 3635

Difficulty: Hard

Paid? No

Companies: N/A

Problem Description

Given a string num representing a positive integer and an integer t, find the smallest zero–free number (i.e. a number whose digits are all nonzero) that is greater than or equal to num such that the product of its digits is divisible by t. If no such number exists, return "-1". For example, if num = "1234" and t = 256, the answer is "1488" because 1×4×8×8 = 256. Note that if num itself already satisfies the product–divisibility requirement, it can be returned.

Key Insights

  • Since digits must be chosen from 1 to 9 (zero is not allowed), each candidate’s product has a factor–structure coming only from the primes 2, 3, 5 and 7.
  • The integer t must have no prime factors besides 2, 3, 5 and 7; otherwise no combination of allowed digits can yield a product divisible by t.
  • It is natural to “factorize” t into the required exponents for 2, 3, 5, and 7, and then reduce these requirements as digits are chosen.
  • A typical approach is to perform digit–DP/backtracking that builds the candidate from left to right while tracking both the “tight” constraint (i.e. matching the given num) and the remaining required factor counts.
  • If a valid candidate with the same number of digits as num cannot be constructed, it may be necessary to try with a longer length.
  • Greedy ideas (for example, to fill in the remaining positions with the lexicographically smallest digits that can “cover” the remaining required factors) are used to complete a partially fixed prefix.
  • Pruning can be achieved by quickly verifying, from the number of positions left, whether it is even possible to supply the missing prime exponents (e.g. each extra digit can contribute at most 3 factors of 2, 2 factors of 3, and 1 factor for 5 and 7).

Space and Time Complexity

Time Complexity: O(N * S) where N is the number of digits (which could be up to 2×10^5) and S is the size of the state (which depends on the required exponents for 2,3,5,7 – relatively small in practice thanks to the pruning). Space Complexity: O(N * S) due to the recursion stack and memoization table.

Solution

The solution follows these major steps:

  1. Factorize t into its prime factors (only 2,3,5,7 are allowed). If any other prime factor is found, return "-1" immediately.
  2. Implement a DFS/backtracking function which takes as state the current digit position, a flag indicating whether we are still “tight” with respect to num, and the remaining required exponents (for 2, 3, 5, 7) that need to be “covered” by future digits.
  3. For every position, if we are “tight” then the next digit to choose starts at the corresponding digit from num; otherwise, start with 1. For each candidate digit (from the allowed range 1–9) try to “update” the remaining requirements (subtracting the digit’s contributions – note that each digit has a fixed prime–exponent contribution, e.g. digit 8 gives three 2’s) and check if it is possible (by verifying that even the best–case contributions from the digits in the later positions are enough).
  4. When the end of the candidate number is reached (i.e. a complete digit string is constructed) check whether all required factors have been covered. If yes, return this candidate.
  5. If no valid candidate with the same number of digits can be built, attempt to build a candidate with one more digit, starting from an empty prefix and using greedily the smallest digits possible to cover the requirements.
  6. DFS memoization is used to cache repeated states identified by the position, the tight constraint, and the remaining counts for the four prime factors.
  7. The “greedy fill” – used when a prefix has been fixed – builds the remainder of the candidate number by always choosing the smallest possible digit that still allows future positions to cover the remaining factor needs.

The outlined approach uses backtracking and greedy filling with heavy pruning (for instance, checking the maximum contribution possible in the remaining positions) to handle the large input sizes. The main trick is to “simulate” digit–DP over the candidate digits while carrying along the “debt” of required prime factors.

Code Solutions

# Python solution using DFS with memoization
# Each digit from 1 to 9 contributes fixed prime factor counts.
def smallestDivisibleDigitProduct(num: str, t: int) -> str:
    # Precompute contributions for each digit 1-9: mapping digit->(c2, c3, c5, c7)
    digit_contrib = {
        1: (0,0,0,0),
        2: (1,0,0,0),
        3: (0,1,0,0),
        4: (2,0,0,0),  # 4 = 2^2
        5: (0,0,1,0),
        6: (1,1,0,0),  # 6 = 2 * 3
        7: (0,0,0,1),
        8: (3,0,0,0),  # 8 = 2^3
        9: (0,2,0,0)   # 9 = 3^2
    }
    
    # Factorize t into exponents for 2,3,5,7.
    req = [0,0,0,0]  # [req2, req3, req5, req7]
    for p, idx in [(2,0), (3,1), (5,2), (7,3)]:
        while t % p == 0:
            req[idx] += 1
            t //= p
    # If any factor remains, no solution is possible.
    if t != 1:
        return "-1"
    
    # Check feasibility: given a number of positions left L, each digit can contribute at most:
    # for prime 2: +3, for 3: +2, for 5 and 7: +1.
    def can_fill(L, r2, r3, r5, r7):
        return (r2 <= 3 * L and r3 <= 2 * L and r5 <= L and r7 <= L)
    
    # Memoization dictionary
    from functools import lru_cache
    # We'll use DFS with parameters: pos, tight (0/1), r2, r3, r5, r7, and fixed length L.
    def dfs(pos, tight, r2, r3, r5, r7, L, digits):
        # If reached the end, check if all requirements are covered
        if pos == L:
            if r2 <= 0 and r3 <= 0 and r5 <= 0 and r7 <= 0:
                return ""
            else:
                return None

        # Prune if even the maximum contribution from remaining digits cannot cover needed factors.
        if not can_fill(L - pos, max(r2, 0), max(r3, 0), max(r5, 0), max(r7, 0)):
            return None

        # Key for memoization
        key = (pos, tight, r2, r3, r5, r7)
        if key in memo:
            return memo[key]
        
        # Determine starting digit based on tight flag.
        start = int(digits[pos]) if tight else 1
        for d in range(start, 10):
            # Calculate new requirements by subtracting the contributions of the chosen digit.
            c2, c3, c5, c7 = digit_contrib[d]
            nr2 = max(r2 - c2, 0)
            nr3 = max(r3 - c3, 0)
            nr5 = max(r5 - c5, 0)
            nr7 = max(r7 - c7, 0)
            new_tight = tight and (d == start)
            # Recurse to fill the rest positions.
            res = dfs(pos+1, new_tight, nr2, nr3, nr5, nr7, L, digits)
            if res is not None:
                ans = str(d) + res
                memo[key] = ans
                return ans
        memo[key] = None
        return None

    # Try candidate numbers for length = len(num) and possibly longer lengths.
    L0 = len(num)
    # Try for lengths starting from L0 upward.
    # We prepare a dummy "digits" string for the tight condition.
    for L in range(L0, L0+2):
        if L == L0:
            digits = num
            memo = {}
            res = dfs(0, True, req[0], req[1], req[2], req[3], L, digits)
            if res is not None:
                return res
        else:
            # For longer length, the candidate is free (not tight), so we use all "1"s as the lower bound.
            digits = "1" * L
            memo = {}
            res = dfs(0, False, req[0], req[1], req[2], req[3], L, digits)
            if res is not None:
                return res
    return "-1"

# Example test cases.
if __name__ == "__main__":
    print(smallestDivisibleDigitProduct("1234", 256))   # Expected output: "1488"
    print(smallestDivisibleDigitProduct("12355", 50))   # Expected output: "12355"
    print(smallestDivisibleDigitProduct("11111", 26))   # Expected output: "-1"
← Back to All Questions