Welcome to Subscribe On Youtube
3345. Smallest Divisible Digit Product I
Description
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
Solutions
Solution 1: Enumeration
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)$.
-
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; } } } } -
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; } } } }; -
class Solution: def smallestNumber(self, n: int, t: int) -> int: for i in count(n): p = 1 x = i while x: p *= x % 10 x //= 10 if p % t == 0: return i -
func smallestNumber(n int, t int) int { for i := n; ; i++ { p := 1 for x := i; x > 0; x /= 10 { p *= x % 10 } if p%t == 0 { return i } } } -
function smallestNumber(n: number, t: number): number { for (let i = n; ; ++i) { let p = 1; for (let x = i; x; x = Math.floor(x / 10)) { p *= x % 10; } if (p % t === 0) { return i; } } }