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 <= 10In #3345 Smallest Divisible Digit Product I, the goal is to find the smallest integer meeting a specific condition related to the product of its digits. Since the constraint involves digit-level computation, a natural strategy is to evaluate candidate numbers and check whether their digit product satisfies the divisibility requirement.
A practical approach is enumeration. Start from the given number and repeatedly check each number in increasing order. For every candidate, compute the product of its digits by extracting digits using modulo and division operations. If the product is divisible by the required value (product % t == 0), the number satisfies the condition and can be returned.
This approach works well because the operation per number is lightweight and digit extraction is fast. The time complexity depends on how many numbers are checked and the number of digits in each candidate. Space usage remains constant since only a few variables are needed during computation.
| Approach | Time Complexity | Space Complexity |
|---|---|---|
| Enumeration with digit product check | O(k * d) where k is the number of checked integers and d is digits per number | O(1) |
NeetCodeIO
Use these hints if you're stuck. Try solving on your own first.
You have to check at most 10 numbers.
Apply a brute-force approach by checking each possible number.
Watch expert explanations and walkthroughs
Jot down your thoughts, approach, and key learnings
Problems of this style can appear in coding interviews as warm-up or screening questions. They test understanding of number manipulation, loops, and basic math logic rather than advanced data structures.
You can repeatedly extract digits using modulo (n % 10) and divide the number by 10. Multiply each extracted digit to maintain the product. This process runs in linear time with respect to the number of digits.
No special data structure is required for this problem. Simple integer variables and basic arithmetic operations are sufficient since the task mainly involves digit manipulation and checking divisibility.
The most straightforward approach is enumeration. Start from the given number and check each number by computing the product of its digits. Once the product is divisible by the required value, that number is the answer.