Skip to main content
Talentd

Smallest Divisible Digit Product II - Solution & Explanation

HardMathStringBacktrackingGreedy12 min readAsked at: Microsoft, Accenture, Google
Practice this 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

Approach Overview

Problem Overview: Given a numeric string and a target value t, you must construct the smallest number greater than or equal to the input such that the product of its digits is divisible by t. The number must be built using digits 0–9 while preserving the smallest possible lexicographic value.

Approach 1: Increment and Check (Brute Force) (Time: O(k * d), Space: O(1))

The straightforward method repeatedly increments the current number and checks whether the product of its digits is divisible by t. Convert the number to digits, multiply them, and verify product % t == 0. This approach works because every candidate is tested directly. However, when the input length grows, the number of increments can explode, especially if the valid answer is far away. The digit product calculation costs O(d) per check where d is the number of digits, making the method impractical for large constraints. Still, it provides a correctness baseline and helps validate optimized solutions.

Approach 2: Backtracking with Greedy Digit Construction (Time: O(9^d) worst case, heavily pruned; Space: O(d))

A more practical strategy builds the result digit by digit using backtracking. First factorize t using number theory insights and track what prime factors the final digit product must contain. While constructing the number, try digits from smallest to largest to keep the result minimal. Each chosen digit contributes factors to the cumulative product. If the remaining positions cannot satisfy the remaining factor requirements, prune the branch immediately. This pruning drastically reduces the search space. The algorithm effectively combines greedy ordering with recursive exploration so that the first valid completion is already the smallest valid number.

The implementation usually processes the number as a string, allowing easy digit replacement and prefix comparison with the original input. Once a prefix exceeds the original number, the remaining digits can be filled greedily with the smallest digits that satisfy the remaining factor constraints.

Recommended for interviews: Start by explaining the increment-and-check baseline to demonstrate problem understanding. Then move to the backtracking + factor tracking approach. Interviewers expect you to reduce the brute-force search space using pruning, greedy ordering, and factor decomposition.

Approach 1: Increment and Check

In this approach, we start from the given number and systematically try to find the smallest zero-free number whose digits' product is divisible by t. We will increment the number and check whether it satisfies the required conditions, replacing any '0' digits with '1' if they appear, since zero-free condition must be maintained.

This C implementation takes the input number as a string and repeatedly increments it until it meets the conditions of being zero-free and having a digit product divisible by t. We ensure zero-free status by replacing any '0' with '1'.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

Time Complexity: O(digit count × iteration limit).
Space Complexity: O(n), where n is the length of the number string.

Try this approach in the editor →

Approach 2: Backtracking Approach

In this approach, we employ backtracking to generate candidate numbers meeting the requirements. By systematically building numbers through potential digits, we ensure the resulting number is zero-free and checks the product divisibility. Unlike incremental changes, this method prevents excessive retries by pruning paths failing early tests.

This Python backtracking solution recursively explores altering digits in the given number. The approach integrates pruning based on immediate product divisibility signals, constructing the smallest potential zero-free number one digit at a time.

Code

Python

Python

Complexity

Time Complexity: Potentially exponential due to exhaustive search but pruned early.
Space Complexity: O(n), for maintaining current number and function call stack.

Try this approach in the editor →

Approach 3: Default Approach

Code

Go

Go

Try this approach in the editor →

Complexity Comparison

ApproachComplexity
Increment and Check

Time Complexity: O(digit count × iteration limit).
Space Complexity: O(n), where n is the length of the number string.

Backtracking Approach

Time Complexity: Potentially exponential due to exhaustive search but pruned early.
Space Complexity: O(n), for maintaining current number and function call stack.

Default Approach—

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Increment and CheckO(k * d)O(1)Baseline or brute-force validation when constraints are very small
Backtracking with Greedy Digit SelectionO(9^d) worst case with strong pruningO(d)General solution for large inputs where pruning based on remaining factors drastically reduces search

Video Solution

3348. Smallest Divisible Digit Product II (Leetcode Hard) • Programming Live with Larry • 742 views views

Watch 1 more video solutions →

Frequently Asked Questions

Is Smallest Divisible Digit Product II easy or hard?
Smallest Divisible Digit Product II is classified as Hard because it combines multiple concepts: digit manipulation, number theory, greedy ordering, and backtracking with pruning. Efficiently reducing the search space is the main challenge.
Smallest Divisible Digit Product II Python/Java solution
Python and Java implementations usually follow the same structure: factorize t, iterate through digits in increasing order, and recursively build the number while maintaining the remaining factor requirements. Python solutions often use recursion and dictionaries, while Java implementations rely on arrays and helper methods for factor tracking.
How to solve Smallest Divisible Digit Product II in O(n)?
A strict O(n) solution is generally not feasible because the algorithm may need to explore multiple digit combinations. Instead, efficient solutions rely on greedy ordering and backtracking with pruning. Factorizing t and tracking remaining prime factors allows the search to skip large portions of the candidate space.
What is the best approach for Smallest Divisible Digit Product II?
The most effective solution uses backtracking combined with greedy digit selection. Factorize the target t and track which prime factors must still appear in the digit product. While constructing the number digit by digit, prune branches that cannot satisfy the remaining factor requirements. This ensures the first valid result is the smallest possible number.
Is Smallest Divisible Digit Product II asked at Google/Amazon/Meta?
Problems involving digit construction, factorization, and constrained search frequently appear in interviews at companies like Google, Amazon, and Meta. Variants that combine number theory with backtracking are especially common in senior-level algorithm rounds.
What data structure is used in Smallest Divisible Digit Product II?
The core implementation typically uses strings or arrays to manipulate digits, along with recursion for backtracking. A map or array may track remaining prime factors of t. These structures make it easy to update the digit product contribution while exploring candidate numbers.
What is the time complexity of Smallest Divisible Digit Product II?
The brute-force increment-and-check approach can take O(k * d) time where k is the number of increments attempted and d is the number of digits. The optimized backtracking solution has a worst-case search of O(9^d), but aggressive pruning based on remaining factor requirements dramatically reduces the actual runtime.

Ready to solve this problem?

Practice Smallest Divisible Digit Product II with our built-in code editor and test cases.

Practice on FleetCode
Previous

Smallest Number With Given Digit Product