LeetCode #3348 — HARD

Smallest Divisible Digit Product II

Break down a hard problem into reliable checkpoints, edge-case handling, and complexity trade-offs.

Solve on LeetCode
The Problem

Problem Statement

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

Example 1:

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:

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:

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 * 105
  • num consists only of digits in the range ['0', '9'].
  • num does not contain leading zeros.
  • 1 <= t <= 1014
Patterns Used
🔀Backtracking→🎯Greedy→

Roadmap

  1. Brute Force Baseline
  2. Core Insight
  3. Algorithm Walkthrough
  4. Edge Cases
  5. Full Annotated Code
  6. Interactive Study Demo
  7. Complexity Analysis
Step 01

Brute Force Baseline

Problem summary: 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".

Baseline thinking

Start with the most direct exhaustive search. That gives a correctness anchor before optimizing.

Pattern signal: Math · Backtracking · Greedy

Example 1

"1234"
256

Example 2

"12355"
50

Example 3

"11111"
26

Related Problems

  • Smallest Number With Given Digit Product (smallest-number-with-given-digit-product)
Step 02

Core Insight

What unlocks the optimal approach

  • <code>t</code> should only have 2, 3, 5 and 7 as prime factors.
  • Find the shortest suffix that must be changed.
  • Try to form the string greedily.
Interview move: turn each hint into an invariant you can check after every iteration/recursion step.
Step 03

Algorithm Walkthrough

Iteration Checklist

  1. Define state (indices, window, stack, map, DP cell, or recursion frame).
  2. Apply one transition step and update the invariant.
  3. Record answer candidate when condition is met.
  4. Continue until all input is consumed.
Use the first example testcase as your mental trace to verify each transition.
Step 04

Edge Cases

Minimum Input
Single element / shortest valid input
Validate boundary behavior before entering the main loop or recursion.
Duplicates & Repeats
Repeated values / repeated states
Decide whether duplicates should be merged, skipped, or counted explicitly.
Extreme Constraints
Largest constraint values
Re-check complexity target against constraints to avoid time-limit issues.
Invalid / Corner Shape
Empty collections, zeros, or disconnected structures
Handle special-case structure before the core algorithm path.
Step 05

Full Annotated Code

Source-backed implementations are provided below for direct study and interview prep.

// Accepted solution for LeetCode #3348: Smallest Divisible Digit Product II
class Solution {
  public String smallestNumber(String num, long t) {
    Pair<Map<Integer, Integer>, Boolean> primeCountResult = getPrimeCount(t);
    Map<Integer, Integer> primeCount = primeCountResult.getKey();
    boolean isDivisible = primeCountResult.getValue();
    if (!isDivisible)
      return "-1";

    Map<Integer, Integer> factorCount = getFactorCount(primeCount);
    if (sumValues(factorCount) > num.length())
      return construct(factorCount);

    Map<Integer, Integer> primeCountPrefix = getPrimeCount(num);
    int firstZeroIndex = num.indexOf('0');
    if (firstZeroIndex == -1) {
      firstZeroIndex = num.length();
      if (isSubset(primeCount, primeCountPrefix))
        return num;
    }

    for (int i = num.length() - 1; i >= 0; --i) {
      final int d = num.charAt(i) - '0';
      // Remove the current digit's factors from primeCountPrefix.
      primeCountPrefix = subtract(primeCountPrefix, FACTOR_COUNTS.get(d));
      final int spaceAfterThisDigit = num.length() - 1 - i;
      if (i > firstZeroIndex)
        continue;
      for (int biggerDigit = d + 1; biggerDigit < 10; ++biggerDigit) {
        // Compute the required factors after replacing with a larger digit.
        Map<Integer, Integer> factorsAfterReplacement = getFactorCount(
            subtract(subtract(primeCount, primeCountPrefix), FACTOR_COUNTS.get(biggerDigit)));
        // Check if the replacement is possible within the available space.
        if (sumValues(factorsAfterReplacement) <= spaceAfterThisDigit) {
          // Fill extra space with '1', if any, and construct the result.
          final int fillOnes = spaceAfterThisDigit - sumValues(factorsAfterReplacement);
          return num.substring(0, i) + // Keep the prefix unchanged.
              biggerDigit +            // Replace the current digit.
              "1".repeat(fillOnes) + // Fill remaining space with '1'.
              construct(factorsAfterReplacement);
        }
      }
    }

    // No solution of the same length exists, so we need to extend the number
    // by prepending '1's and adding the required factors.
    Map<Integer, Integer> factorsAfterExtension = getFactorCount(primeCount);
    return "1".repeat(num.length() + 1 - sumValues(factorsAfterExtension)) +
        construct(factorsAfterExtension);
  }

  private static final Map<Integer, Map<Integer, Integer>> FACTOR_COUNTS = Map.of(
      0, Map.of(), 1, Map.of(), 2, Map.of(2, 1), 3, Map.of(3, 1), 4, Map.of(2, 2), 5, Map.of(5, 1),
      6, Map.of(2, 1, 3, 1), 7, Map.of(7, 1), 8, Map.of(2, 3), 9, Map.of(3, 2));

  // Returns the prime count of t and if t is divisible by 2, 3, 5, 7.
  private Pair<Map<Integer, Integer>, Boolean> getPrimeCount(long t) {
    Map<Integer, Integer> count = new HashMap<>(Map.of(2, 0, 3, 0, 5, 0, 7, 0));
    for (int prime : new int[] {2, 3, 5, 7}) {
      while (t % prime == 0) {
        t /= prime;
        count.put(prime, count.get(prime) + 1);
      }
    }
    return new Pair<>(count, t == 1);
  }

  // Returns the prime count of `num`.
  private Map<Integer, Integer> getPrimeCount(String num) {
    Map<Integer, Integer> count = new HashMap<>(Map.of(2, 0, 3, 0, 5, 0, 7, 0));
    for (final char c : num.toCharArray()) {
      Map<Integer, Integer> digitFactors = FACTOR_COUNTS.get(c - '0');
      for (Map.Entry<Integer, Integer> entry : digitFactors.entrySet()) {
        final int prime = entry.getKey();
        final int freq = entry.getValue();
        count.merge(prime, freq, Integer::sum);
      }
    }
    return count;
  }

  private Map<Integer, Integer> getFactorCount(Map<Integer, Integer> count) {
    // 2^3 = 8
    final int count8 = count.get(2) / 3;
    final int remaining2 = count.get(2) % 3;
    // 3^2 = 9
    final int count9 = count.get(3) / 2;
    int count3 = count.get(3) % 2;
    // 2^2 = 4
    int count4 = remaining2 / 2;
    int count2 = remaining2 % 2;
    // Combine 2 and 3 to 6 if both are present
    int count6 = 0;
    if (count2 == 1 && count3 == 1) {
      count2 = 0;
      count3 = 0;
      count6 = 1;
    }
    // Combine 3 and 4 to 2 and 6 if both are present
    if (count3 == 1 && count4 == 1) {
      count2 = 1;
      count6 = 1;
      count3 = 0;
      count4 = 0;
    }
    return Map.of(2, count2, 3, count3, 4, count4, 5, count.get(5), 6, count6, 7, count.get(7), 8,
                  count8, 9, count9);
  }

  private String construct(Map<Integer, Integer> factors) {
    StringBuilder sb = new StringBuilder();
    for (int digit = 2; digit < 10; ++digit)
      sb.append(String.valueOf(digit).repeat(factors.get(digit)));
    return sb.toString();
  }

  // Returns true if a is a subset of b.
  private boolean isSubset(Map<Integer, Integer> a, Map<Integer, Integer> b) {
    for (Map.Entry<Integer, Integer> entry : a.entrySet())
      if (b.get(entry.getKey()) < entry.getValue())
        return false;
    return true;
  }

  // Returns a - b.
  private Map<Integer, Integer> subtract(Map<Integer, Integer> a, Map<Integer, Integer> b) {
    Map<Integer, Integer> res = new HashMap<>(a);
    for (Map.Entry<Integer, Integer> entry : b.entrySet()) {
      final int key = entry.getKey();
      final int value = entry.getValue();
      res.put(key, Math.max(0, res.get(key) - value));
    }
    return res;
  }

  // Returns the sum of the values in `count`.
  private int sumValues(Map<Integer, Integer> count) {
    return count.values().stream().mapToInt(Integer::intValue).sum();
  }
}
Step 06

Interactive Study Demo

Use this to step through a reusable interview workflow for this problem.

Press Step or Run All to begin.
Step 07

Complexity Analysis

Time
O(n!)
Space
O(n)

Approach Breakdown

EXHAUSTIVE
O(nⁿ) time
O(n) space

Generate every possible combination without any filtering. At each of n positions we choose from up to n options, giving nⁿ total candidates. Each candidate takes O(n) to validate. No pruning means we waste time on clearly invalid partial solutions.

BACKTRACKING + PRUNING
O(n!) time
O(n) space

Backtracking explores a decision tree, but prunes branches that violate constraints early. Worst case is still factorial or exponential, but pruning dramatically reduces the constant factor in practice. Space is the recursion depth (usually O(n) for n-level decisions).

Shortcut: Backtracking time = size of the pruned search tree. Focus on proving your pruning eliminates most branches.
Coach Notes

Common Mistakes

Review these before coding to avoid predictable interview regressions.

Overflow in intermediate arithmetic

Wrong move: Temporary multiplications exceed integer bounds.

Usually fails on: Large inputs wrap around unexpectedly.

Fix: Use wider types, modular arithmetic, or rearranged operations.

Missing undo step on backtrack

Wrong move: Mutable state leaks between branches.

Usually fails on: Later branches inherit selections from earlier branches.

Fix: Always revert state changes immediately after recursive call.

Using greedy without proof

Wrong move: Locally optimal choices may fail globally.

Usually fails on: Counterexamples appear on crafted input orderings.

Fix: Verify with exchange argument or monotonic objective before committing.

Related Problems
#2178Maximum Split of Positive Even Integersmedium→#89Gray Codemedium→#282Expression Add Operatorshard→#357Count Numbers with Unique Digitsmedium→#670Maximum Swapmedium→