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

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Smallest Divisible Digit Product I

Difficulty: Easy

Problem 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.

Key Insights

  • The product of the digits of a number can be calculated by iterating through each digit.
  • If any digit is zero, the product is zero, which is divisible by any non-zero t.
  • To find the smallest number that satisfies the condition, start from n and incrementally check each subsequent number until the condition is met.
  • The constraints are small, allowing for a simple brute force approach to be efficient.

Space and Time Complexity

Time Complexity: O(1) in the context of the given constraints (1 <= n <= 100), but O(k) in general where k is the count of numbers checked until a solution is found. Space Complexity: O(1) since we are using a constant amount of space regardless of the input size.

Solution

The algorithm iterates through numbers starting from n. For each number, it calculates the product of its digits and checks if this product is divisible by t. If it is, the current number is returned as the result. The digits can be extracted by converting the number to a string or by using modulo and division operations.

Code Solutions

def smallest_divisible_digit_product(n, t):
    def digit_product(num):
        product = 1
        while num > 0:
            digit = num % 10
            product *= digit
            num //= 10
        return product

    while True:
        if digit_product(n) % t == 0:
            return n
        n += 1
← Back to All Questions