3345. Smallest Divisible Digit Product I

Math
Enumeration
Simulation

TIME

O(A * d)

SPACE

O(1)

Intuition

With n <= 100 and t <= 10, just scan upward from n and return the first number whose digit product is divisible by t. The search is guaranteed short: any number containing a 0 digit has digit product 0, which is divisible by every t, and such numbers (e.g. the next multiple of 10) are never far away.

Approach

Starting at x = n, compute the product of x's digits.
If that product is divisible by t, return x.
Otherwise increment x and repeat.

Complexity

Time: O(A · d) where A = answer − n (small) and d = digit count
Space: O(1)

Edge Cases

t = 1 → every number qualifies → answer is n
Number with a 0 digit → product 0, divisible by any t
n itself already satisfies (Example 1) → return n
Worst case still bounded: the next multiple of 10 always works

Code

class Solution:
    def smallestNumber(self, n: int, t: int) -> int:
        """
        3345. Smallest Divisible Digit Product I
        Time: O(A * d)
        Space: O(1)
        """
        x = n
        while True:
            product = 1
            for ch in str(x):
                product *= int(ch)
            if product % t == 0:
                return x
            x += 1

/**
 * 3345. Smallest Divisible Digit Product I
 * Time: O(A * d)
 * Space: O(1)
 */
class Solution {
    public int smallestNumber(int n, int t) {
        int x = n;
        while (true) {
            int product = 1;
            for (int y = x; y > 0; y /= 10) {
                product *= y % 10;
            }
            if (product % t == 0) {
                return x;
            }
            x++;
        }
    }
}