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 <= 10Problem 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.
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.
Time Complexity: O(1) in practice, since the maximum number of iterations is limited by the small input constraint.
Space Complexity: O(1).
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.
Time Complexity: O(1) for the average case with early termination.
Space Complexity: O(1).
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).
Python
Java
C++
Go
TypeScript
| 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 | — |
| 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 |
3345. Smallest Divisible Digit Product I || C++ solution || Leetcode • CodeQuest • 187 views views
Watch 4 more video solutions →Practice Smallest Divisible Digit Product I with our built-in code editor and test cases.
Practice on FleetCode