# Smallest Divisible Digit Product II **Difficulty:** HARD [External](https://leetcode.com/problems/smallest-divisible-digit-product-ii) Canonical: https://scaleengineer.com/dsa/problems/smallest-divisible-digit-product-ii **Patterns:** [Math](https://scaleengineer.com/dsa/patterns/math), [Greedy](https://scaleengineer.com/dsa/patterns/greedy), [Backtracking](https://scaleengineer.com/dsa/patterns/backtracking), [Number Theory](https://scaleengineer.com/dsa/patterns/number-theory) **Data structures:** String --- ## Problem 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` # Approaches ## Recursive Backtracking with Memoization (Digit DP) This approach attempts to build the target number digit by digit from left to right using a standard recursive backtracking method, often referred to as 'Digit DP'. The state of the recursion includes the current index, the remaining prime factor requirements, and a 'tight' constraint flag to ensure the generated number is greater than or equal to the input `num`. Memoization is used to cache the results of subproblems. **Time:** O(N * r2 * r3 * r5 * r7 * 10). The recursive function explores each state once due to memoization, and in each state, it iterates through up to 9 possible digits. This is too slow. · **Space:** O(N * r2 * r3 * r5 * r7), where N is the length of `num` and r_i are the maximum powers of primes in `t`. This is too large for the given constraints. **Pros:** It is a standard and often intuitive approach for problems involving finding numbers with specific properties within a certain range.; The logic correctly finds the lexicographically smallest number by building it from left to right and trying smaller digits first. **Cons:** The state space for memoization is prohibitively large due to the length of `num` (`N`) and the range of factor counts (`r2, r3, r5, r7`). The complexity `O(N * r2 * r3 * r5 * r7)` is too high for the given constraints.; Results in a 'Time Limit Exceeded' or 'Memory Limit Exceeded' error on platforms with strict constraints. ### Explanation The core of this method is a recursive function that constructs the result string. The function tries to determine the best digit to place at each position, starting from the most significant digit. The state of the recursion needs to track: 1. `index`: The current position in the number string we are building. 2. `p2, p3, p5, p7`: The count of prime factors (2, 3, 5, 7) that still need to be covered by the product of the remaining digits. 3. `isTight`: A boolean flag. If `true`, the digit at the current `index` can be from `num[index]` to '9'. If we choose a digit `d > num[index]`, the `isTight` constraint is lifted for subsequent positions (`isTight` becomes `false`). If `isTight` is already `false`, we can choose any digit from '1' to '9'. The function's goal is to return the smallest possible suffix that can be formed from `index` onwards, given the factor requirements. If no such suffix exists, it returns a special value indicating failure. To avoid re-calculating the same state, a multi-dimensional array `memo[index][p2][p3][p5][p7][isTight]` is used. However, with `num.length` up to `2 * 10^5`, the size of this memoization table becomes impractically large, making the approach infeasible. ```java // Conceptual code for the recursive approach class Solution { String num; int[] tFactors; String[][][][][] memo; public String solve(int index, int p2, int p3, int p5, int p7, boolean isTight) { if (p2 <= 0 && p3 <= 0 && p5 <= 0 && p7 <= 0) { // Requirement met, fill rest with '1's StringBuilder ones = new StringBuilder(); for (int i = 0; i < num.length() - index; i++) { ones.append('1'); } return ones.toString(); } if (index == num.length()) { return null; // Failed to meet requirement } if (memo[index][p2][p3][p5][p7][isTight ? 1 : 0] != null) { return memo[index][p2][p3][p5][p7][isTight ? 1 : 0]; } String ans = null; int lowerBound = isTight ? (num.charAt(index) - '0') : 1; for (int d = lowerBound; d <= 9; d++) { if (d == 0) continue; int[] digitFactors = getFactors(d); boolean newIsTight = isTight && (d == lowerBound); String res = solve(index + 1, p2 - digitFactors[0], p3 - digitFactors[1], p5 - digitFactors[2], p7 - digitFactors[3], newIsTight); if (res != null) { ans = d + res; break; // Found the smallest digit `d`, so we can stop } } return memo[index][p2][p3][p5][p7][isTight ? 1 : 0] = ans; } // Helper methods getFactors, etc. } ``` ### Algorithm - Define a recursive function, for example, `solve(index, p2, p3, p5, p7, isTight)`. - `index`: The current digit position being filled (from left to right). - `p2, p3, p5, p7`: The remaining counts of prime factors (2, 3, 5, 7) needed. - `isTight`: A boolean flag indicating if we are restricted to digits `>= num[index]`. If false, we can use any digit from 1-9. - The function explores placing digits `d` from a valid range at the current `index`. - For each `d`, it makes a recursive call for `index + 1` with updated parameters. - The base case is when `index` reaches the end of the number. If all factor requirements are met (`p_i <= 0`), it signifies a valid number. - Memoization is used to store results for states `(index, p2, p3, p5, p7, isTight)` to avoid recomputation. ## Dynamic Programming on Prime Factors with Constructive Search This efficient approach combines precomputation with a constructive search. The core idea is that the optimal suffix of a number (the part that needs to satisfy remaining divisibility conditions) is independent of the prefix. We can precompute the best possible suffixes for all possible factor requirements using dynamic programming. Then, we search for the smallest number greater than or equal to `num` by trying to modify `num` at the rightmost possible position, and using our precomputed table to find the optimal suffix. **Time:** O(F * log(F) * L_max + N), where F is the DP state space size, L_max is max digit string length, and N is `num.length`. The first term is for precomputation, the second for the search. · **Space:** O(F * L_max), where F is the DP state space size (~500,000) and L_max is the max length of a digit string (~50). This is significant but constant with respect to `num`'s length. **Pros:** Highly efficient for large `num` as the main search is linear in `num.length` after precomputation.; Guaranteed to find the optimal solution by systematically exploring modifications from right to left.; The precomputation step is independent of `num` and `t`'s magnitude (only depends on prime factor powers), making it reusable for multiple queries. **Cons:** The implementation is complex, involving multiple components: prime factorization, a Dijkstra-based DP precomputation, and a constructive search for the final number.; The DP precomputation can be resource-intensive, although it's a one-time cost independent of the input `num`'s size. ### Explanation This method breaks the problem down into a manageable precomputation step and a final construction step. ### 1. Precomputation using DP on Factors First, we observe that the product of digits only involves prime factors 2, 3, 5, and 7. If `t` has other prime factors, we return "-1". We find the required powers of these primes in `t`, let's say `(r2, r3, r5, r7)`. The subproblem is: what is the best set of digits to produce a certain combination of prime factors? We define "best" as having the minimum number of digits, and for a tie, being lexicographically smallest when sorted. We can solve this using Dijkstra's algorithm on the state space of factor counts `(p2, p3, p5, p7)`. - **State:** A tuple `(p2, p3, p5, p7)` representing factor counts. - **Distance:** A pair `(length, string)`, where `length` is the number of digits and `string` is the sorted string of digits. - **Priority Queue:** Stores `(distance, state)`, ordered by distance. We initialize distance to `(0, "")` for state `(0,0,0,0)` and infinity for all others. The algorithm explores states, adding digits 2-9, and updates distances if a shorter or lexicographically smaller digit string is found. The result is a table, `dp[p2][p3][p5][p7]`, storing the best digit string for each factor requirement. ### 2. Constructing the Solution We find the answer by considering two possibilities for the result's length. **Case A: Solution has the same length as `num`** We want the smallest zero-free number `x >= num` of length `n`. 1. If `num` contains '0's, we must find a larger number. The smallest zero-free number `>= num` can be found by finding the first '0' at index `k`, then finding the rightmost non-'9' digit at `j < k`, incrementing it, and setting digits from `j+1` to `n-1` to '1'. This becomes our new base `num`. If no such `j` exists, no solution of length `n` is possible. 2. We check if this new `num` is a solution. If not, we iterate from `i = n-1` down to `0`. For each `i`, we try digits `d` from `num[i] + 1` to `9`. This forms a prefix `num[0...i-1]d`. 3. We calculate the prime factors provided by this prefix and determine the remaining factors needed. 4. We query our `dp` table for the best suffix for these remaining factors. To do this, we check all `dp` states that satisfy the requirement and take the best one. 5. If the length of this optimal suffix is less than or equal to the remaining space (`n-1-i`), we've found a candidate. We pad with '1's, sort the suffix digits, and form the number. The first such number found is the answer for this case. **Case B: Solution is longer than `num`** The smallest number longer than `num` must have the minimum possible length `m > n`. The minimum number of digits required to satisfy `t` is given by the length of the optimal string for `(r2, r3, r5, r7)`, let's call it `s`. So, `m = max(n + 1, s.length())`. The result is formed by sorting the digits of `s` along with `m - s.length()` ones. Finally, we compare the results from Case A and B and return the smaller one. ```java // Conceptual code for the efficient approach class Solution { // DP table and factor arrays private String[][][][] dp; private int[] tFactors; public String smallestDivisibleDigitProductII(String num, long t) { // 1. Factorize t and check for invalid primes // ... // 2. Precompute DP table using Dijkstra precomputeDpTable(); // 3. Find solution for length n String solN = findSolutionOfLengthN(num); // 4. Find solution for length > n String solNPlus = findSolutionOfGreaterLength(num.length()); // 5. Compare and return the best result if (solN == null) return solNPlus; if (solNPlus == null) return solN; if (solN.length() < solNPlus.length()) return solN; if (solN.length() > solNPlus.length()) return solNPlus; return solN.compareTo(solNPlus) < 0 ? solN : solNPlus; } private void precomputeDpTable() { /* ... Dijkstra implementation ... */ } private String findSolutionOfLengthN(String num) { /* ... Case A logic ... */ return null; } private String findSolutionOfGreaterLength(int n) { /* ... Case B logic ... */ return null; } } ``` ### Algorithm - **Prime Factorization:** First, find the prime factorization of `t`. If `t` has any prime factor greater than 7, no solution exists. Let the required counts of factors 2, 3, 5, 7 be `(r2, r3, r5, r7)`. - **DP Precomputation:** Create a DP table `dp[p2][p3][p5][p7]` that stores the optimal (shortest, then lexicographically smallest) string of digits whose product yields exactly `p2` factors of 2, `p3` of 3, etc. This table can be populated using Dijkstra's algorithm on the state space of factor counts. - **Handle Two Cases:** The problem is split into finding the smallest solution of length `n` (same as `num`) and finding the smallest solution of length `> n`. - **Case 1 (length `n`):** - Handle any '0's in `num` by creating a new, larger, zero-free `startNum`. - Iterate from the rightmost digit of `startNum` (`i = n-1` to `0`). - At each position `i`, try to use a digit `d` greater than `startNum[i]`. - For the prefix `startNum[0...i-1]d`, calculate the remaining factors needed. - Look up the optimal suffix for these factors in the precomputed `dp` table. - If the suffix fits in the remaining length, construct the number. The first one found is the smallest of length `n`. - **Case 2 (length `> n`):** - Find the optimal digit string `s` for the full requirements `(r2, r3, r5, r7)` from the `dp` table. - The minimum length of a solution longer than `n` is `m = max(n + 1, s.length())`. - Construct the smallest number of length `m` using digits from `s` and padding with '1's. - **Final Result:** Compare the results from both cases and return the overall smallest number.