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 <= 100
1 <= t <= 10
My Solution
We can solve this problem by extracting the digits of n at every iteration and finding their product. If it is divisible by t, we return that number. Otherwise, we increment n and continue until we find a number that is divisible by t.
Time Complexity is O(1), because looking at the constraints, the maximum number of iterations we can run for is 10. Always within 10 iterations, one of the digits of n will be equal to t, which makes it divisible by t. Also n is only between 1 and 100, so the digit product will only take 3 iterations at maximum. Space complexity is O(1) because we only require constant extra space.
class Solution {
public int smallestNumber(int n, int t) {
n = Math.max(n, t);
while (prod(n) % t != 0) {
n++;
}
return n;
}
public int prod(int n) {
int out = 1;
while (n > 0) {
out *= n % 10;
n /= 10;
}
return out;
}
}