Watch 5 video solutions for Smallest Divisible Digit Product I, a easy level problem involving Math, Enumeration. This walkthrough by CodeQuest has 187 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
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.
| 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 |