Problem Statement in English

You’re given two positive integers num and t. You need to find the smallest integer greater than or equal to num such that the product of its digits is divisible by t. If no such integer exists, return -1.

Approach

It’s guaranteed that if one digit becomes zero, the product of the digits will be zero, which is divisible by any positive integer. Therefore, we can simply increment the number by one, and it’s guaranteed to find the answer within 10 steps.

And we’re done!

Solution in Python


class Solution:
    def smallestNumber(self, num: int, t: int) -> int:
        def get_digit_product(x: int) -> int:
            product = 1
            for digit in str(x):
                product *= int(digit)
                if product == 0:
                    break
            return product

        curr = num
        while True:
            if get_digit_product(curr) % t == 0:
                return curr
            curr += 1

Complexity

  • Time: $O(1)$
    Since we are guaranteed to find the answer within $10$ steps.

  • Space: $O(1)$
    Since we are using a constant amount of space.

Mistakes I Made

I had to look this up.

And we are done.