We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Smallest Divisible Digit Product I

Number: 3626

Difficulty: Easy

Paid? No

Companies: N/A

Problem Description

Find the smallest number greater than or equal to n such that the product of its digits is divisible by t.

Key Insights

  • We need to find an integer x starting from n such that when you compute the product of its digits, the result is divisible by t.
  • A brute-force approach is acceptable given that n is at most 100 and t is at most 10.
  • If any digit is 0, the product becomes 0, which will always be divisible by t (since t is non-zero).
  • The simple approach is to check each number in sequence and return the first one that satisfies the condition.

Space and Time Complexity

Time Complexity: O(m * d) where m is the number of numbers checked until a solution is found and d is the number of digits in each number. Space Complexity: O(1) since constant extra space is used.

Solution

The solution iterates through the numbers starting at n. For each number, a helper function calculates the product of its digits. This is done either by converting the number to a string or by iterative modulus operations. The product is then checked to see if it is divisible by t. Due to the small input constraints, this brute-force enumeration provides an efficient solution.

Code Solutions

def smallestDivisibleDigitProduct(n: int, t: int) -> int:
    # Helper function to compute the product of the digits of a number
    def digit_product(num: int) -> int:
        product = 1
        while num > 0:
            digit = num % 10  # Extract the last digit
            product *= digit
            num //= 10      # Remove the last digit
        return product

    current = n
    while True:
        if digit_product(current) % t == 0:
            return current
        current += 1

# Example usage:
print(smallestDivisibleDigitProduct(10, 2))  # Expected output: 10
print(smallestDivisibleDigitProduct(15, 3))  # Expected output: 16
← Back to All Questions