Smallest Divisible Digit Product I - Solution & Explanation
Problem Statement
You are given two integers n and t. Return the smallest number greater than or equal to n such that the product of its digits is divisible by t.
Example 1:
Input: n = 10, t = 2
Output: 10
Explanation:
The digit product of 10 is 0, which is divisible by 2, making it the smallest number greater than or equal to 10 that satisfies the condition.
Example 2:
Input: n = 15, t = 3
Output: 16
Explanation:
The digit product of 16 is 6, which is divisible by 3, making it the smallest number greater than or equal to 15 that satisfies the condition.
Constraints:
1 <= n <= 1001 <= t <= 10
Approach Overview
Problem Overview: Given integers n and t, return the smallest integer greater than or equal to n such that the product of its digits is divisible by t. The task is essentially checking numbers sequentially and verifying whether their digit product satisfies the divisibility condition.
Approach 1: Brute Force Enumeration (O(k * d) time, O(1) space)
Start from n and increment the number one by one until a valid candidate is found. For each number, compute the product of its digits by repeatedly extracting digits using modulo and division operations. After computing the product, check whether product % t == 0. If true, return that number immediately. Each check processes d digits where d is the number of digits, and k represents how many numbers you test before finding a valid one.
This method relies on simple iteration and digit manipulation, making it straightforward to implement. It works well because the constraints are small enough that the search typically terminates quickly. The approach mainly uses basic math operations and simple enumeration of candidates.
Approach 2: Direct Check with Early Termination (O(k * d) time, O(1) space)
This optimization keeps the same enumeration idea but improves how the digit product is computed. While multiplying digits, continuously check divisibility against t. If the intermediate product already becomes divisible by t, further digit processing is unnecessary and you can stop early. Another useful observation: if a digit 0 appears, the entire product becomes zero, which is divisible by any positive t, so the number immediately qualifies.
During digit extraction, update the running product and apply early termination rules whenever possible. This avoids multiplying all digits for many candidates, especially when numbers contain zero or when the product quickly reaches a multiple of t. The algorithm still scans numbers sequentially, but each check often finishes faster in practice.
Recommended for interviews: Start with the brute force explanation to show you understand the direct interpretation of the problem. Then mention the early-termination optimization while computing the digit product. Interviewers typically expect this improvement because it reduces unnecessary work while keeping the implementation simple and constant-space.
Approach 1: Brute Force Approach
This approach involves iterating through each number starting from n and calculating the product of its digits. If the product is divisible by t, then that number is returned as the answer. This is the straightforward solution and can be implemented efficiently given the constraints of the problem.
The function digitProduct calculates the product of the digits of a number. The main function smallestNumber iteratively checks each integer starting from n to find the smallest number whose digit product is divisible by t.
Complexity
Time Complexity: O(1) in practice, since the maximum number of iterations is limited by the small input constraint.
Space Complexity: O(1).
Approach 2: Direct Check with Early Termination
This approach checks each number starting from n and terminates early when a number with digit '0' in it is found, as its digit product will be zero and divisible by any t.
This optimized C code provides an early exit if a zero digit is found, improving performance when possible.
Complexity
Time Complexity: O(1) for the average case with early termination.
Space Complexity: O(1).
Approach 3: Enumeration
We note that within every 10 numbers, there will definitely be an integer whose digit product is 0. Therefore, we can directly enumerate integers greater than or equal to n until we find an integer whose digit product is divisible by t.
The time complexity is O(log n), and the space complexity is O(1).
Code
Python
Java
C++
Go
TypeScript
Complexity Comparison
| Approach | Complexity |
|---|---|
| Brute Force Approach | Time Complexity: O(1) in practice, since the maximum number of iterations is limited by the small input constraint. |
| Direct Check with Early Termination | Time Complexity: O(1) for the average case with early termination. |
| Enumeration | — |
Detailed Complexity Analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Brute Force Enumeration | O(k * d) | O(1) | Simple implementation when constraints are small and straightforward enumeration is acceptable |
| Direct Check with Early Termination | O(k * d) | O(1) | Preferred in practice to reduce unnecessary digit multiplications during checks |
Video Solution
3345. Smallest Divisible Digit Product I || C++ solution || Leetcode • CodeQuest • 197 views views
Watch 3 more video solutions →Frequently Asked Questions
Is Smallest Divisible Digit Product I easy or hard?
Smallest Divisible Digit Product I Python/Java solution
How to solve Smallest Divisible Digit Product I in O(n)?
What is the best approach for Smallest Divisible Digit Product I?
Is Smallest Divisible Digit Product I asked at Google/Amazon/Meta?
What data structure is used in Smallest Divisible Digit Product I?
What is the time complexity of Smallest Divisible Digit Product I?
Ready to solve this problem?
Practice Smallest Divisible Digit Product I with our built-in code editor and test cases.
Practice on FleetCode