Smallest Divisible Digit Product I solution in Python

Problem Description

Welcome to the world of numbers, where we play hide and seek with digits! The problem at hand is the “Smallest Divisible Digit Product I.” Imagine you’re at a party, and you want to find the smallest number that can be formed using digits that, when multiplied together, give you a product divisible by a given number t. Sounds easy, right? Well, it’s like trying to find a needle in a haystack, except the haystack is made of numbers, and the needle is… well, still a number!

In simpler terms, given two integers n and t, you need to find the smallest number greater than or equal to n such that the product of its digits is divisible by t. If you think this is a walk in the park, just wait until you start counting those digits!

Code Solution


class Solution:
    def smallestNumber(self, n: int, t: int) -> int:
        return next(num for num in range(n, n + 10)
                    if self._getDigitProd(num) % t == 0)

    def _getDigitProd(self, num: int) -> int:
        digitProd = 1
        while num > 0:
            digitProd *= num % 10
            num //= 10
        return digitProd

Approach

The approach here is straightforward yet clever. The code iterates through numbers starting from n to n + 10 and checks if the product of the digits of each number is divisible by t. The helper function _getDigitProd calculates the product of the digits of a number. The first number that meets the criteria is returned. It’s like a digital scavenger hunt!

Time and Space Complexity

Complexity Type	Complexity
Time Complexity	O(1)
Space Complexity	O(1)

Real-World Example

Imagine you’re at a grocery store, and you want to buy a pack of gum. You have a budget (let’s say t), and you want to find the smallest pack of gum that fits your budget. Each pack has a price (like the digits of a number), and you want to ensure that the total price is divisible by your budget. This problem is akin to that scenario, where you’re trying to find the smallest number (or pack) that meets your criteria.