Smallest Divisible Digit Product I
EasyPrompt
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
Approaches
2 approaches with complexity analysis and trade-offs.
This method involves pre-calculating the digit products for a range of numbers and storing them. When a query comes, it scans through the pre-computed values starting from n to find the first number that satisfies the divisibility condition. This approach trades space for time, aiming to speed up repeated queries by avoiding re-computation.
Algorithm
- Define a constant
LIMIT(e.g., 200) as the upper bound for pre-computation.\n2. Create a static arraydigitProductsof sizeLIMIT + 1.\n3. In a static block, iterate fromi = 1toLIMIT.\n4. For eachi, calculate its digit product and store it indigitProducts[i].\n5. In the main function, iterate withifromntoLIMIT.\n6. Check ifdigitProducts[i]is divisible byt.\n7. If it is, returnias the result.\n8. If the loop finishes without finding an answer (unlikely), implement a fallback to check numbers greater thanLIMIT.
Walkthrough
Given the small constraints (n <= 100), the answer is expected to be a relatively small number. We can establish a fixed upper limit, for instance, 200, which should comfortably contain the answer for any valid input.\nAn array, let's call it digitProducts, is used to store the product of digits for each number from 1 up to this limit.\nThis array is populated once, possibly in a static initializer block. For each number i in the range, its digit product is calculated and stored at digitProducts[i].\nThe smallestDivisibleDigitProduct function then iterates from n up to the limit. For each number i, it retrieves the pre-computed product digitProducts[i] and checks if it's divisible by t.\nThe first number i that satisfies digitProducts[i] % t == 0 is the smallest such number greater than or equal to n, so it is returned.\nA fallback mechanism for numbers beyond the limit can be included for robustness, although it's unlikely to be triggered with the given constraints.\njava\nclass Solution {\n private static final int LIMIT = 200;\n private static final long[] digitProducts = new long[LIMIT + 1];\n\n static {\n digitProducts[0] = 0;\n for (int i = 1; i <= LIMIT; i++) {\n digitProducts[i] = calculateDigitProduct(i);\n }\n }\n\n private static long calculateDigitProduct(int n) {\n if (n == 0) return 0;\n long product = 1;\n int temp = n;\n while (temp > 0) {\n int digit = temp % 10;\n if (digit == 0) return 0; // Optimization\n product *= digit;\n temp /= 10;\n }\n return product;\n }\n\n public long smallestDivisibleDigitProduct(int n, int t) {\n for (int i = n; i <= LIMIT; i++) {\n if (digitProducts[i] % t == 0) {\n return i;\n }\n }\n // Fallback for cases where answer > LIMIT\n long num = LIMIT + 1;\n while (true) {\n if (calculateDigitProduct((int)num) % t == 0) {\n return num;\n }\n num++;\n }\n }\n}\n
Complexity
Time
Pre-computation: `O(L * log L)` where `L` is the limit. Query: `O(L - n)`. For a single execution, the total time is dominated by pre-computation, making it less efficient than a direct approach for the given problem scale.
Space
`O(L)` to store the pre-computed digit products, where `L` is the chosen limit. Since `L` is a constant, this can be considered `O(1)`.
Trade-offs
Pros
Efficient for multiple test cases or queries, as the expensive calculations are done only once.
The lookup time for each query is fast, involving just an array access and a check.
Cons
Requires extra space to store the pre-computed values (
O(LIMIT)).The pre-computation step is an upfront cost which might be slower than a direct approach if only one query is made.
It relies on a hardcoded limit, which might fail if the constraints were larger.
Solutions
Solution
class Solution {public int smallestNumber(int n, int t) { for (int i = n;; ++i) { int p = 1; for (int x = i; x > 0; x /= 10) { p *= (x % 10); } if (p % t == 0) { return i; } } }}Video walkthrough
Newsletter
One sharp idea, every week
System design and interview prep — short enough to finish.
No spam. Unsubscribe anytime.
Practice
Same difficulty — related problems to reinforce the pattern.