Taro Logo

Smallest Divisible Digit Product I

Easy
Asked by:
Profile picture
8 views
Topics:
Greedy Algorithms

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.

Example 1:

Input: n = 10, t = 2

Output: 10

Explanation:

The digit product of 10 is 0, which is divisible by 2, making it the smallest number greater than or equal to 10 that satisfies the condition.

Example 2:

Input: n = 15, t = 3

Output: 16

Explanation:

The digit product of 16 is 6, which is divisible by 3, making it the smallest number greater than or equal to 15 that satisfies the condition.

Constraints:

  • 1 <= n <= 100
  • 1 <= t <= 10

Solution


Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

  1. Must the digits multiply to the target exactly, rather than to a multiple of the target?
  2. Should a target from one through nine return that same one-digit number?
  3. Is ten the intended answer for a target product of zero?
  4. What should the factoring method return when a factor larger than nine remains?
  5. Does smallest mean the smallest numeric value, favoring fewer digits and then the smallest left-to-right order?

Brute Force Solution

Approach

This scan starts at one and moves upward through the positive integers. For each integer it multiplies the digits, treating a zero digit as a product of zero. It returns the first integer whose digit product equals the target.

Here's how the algorithm would work step-by-step:

  1. Start the current integer at one.
  2. Copy it into a temporary value and start a product at one.
  3. While the temporary value is positive, peel off the last digit.
  4. If that digit is zero, set the product to zero and stop peeling.
  5. Otherwise multiply the product by the digit and drop the digit from the temporary value.
  6. Return the current integer when the product equals the target.
  7. Otherwise add one and repeat.

Code Implementation

def smallest_digit_product_brute_force(target_product):
    current_number = 1
    while True:
        # We need to calculate the product of the digits for the current number.
        temp_number = current_number
        product_of_digits = 1
        while temp_number > 0:
            digit = temp_number % 10

            # If any digit is zero, the product becomes zero, so we must handle this.
            if digit == 0:
                product_of_digits = 0
                break
            product_of_digits *= digit
            temp_number //= 10
        
        # This check determines if the current number's digit product matches our goal.
        if product_of_digits == target_product:
            return current_number
        
        current_number += 1

Big(O) Analysis

Time Complexity
O(A log A) – Let A be the smallest positive integer whose digits multiply to the target. The loop examines every integer from one through A, with no faster jump. Each integer has a number of digits logarithmic in its value, and peeling those digits is proportional to that count. Values up to A have at most about log A digits. Multiplying A iterations by log A digit steps gives O(A log A).
Space Complexity
O(log A) – Only a few integers are stored: the current value, the temporary copy, a digit, and the running product. The current value grows up to A, so writing it down takes a logarithmic number of digits. No list of earlier integers is kept. Digit peeling reuses the same temporary slot. Extra space is O(log A).

Optimal Solution

Approach

Targets below ten are answered directly, with zero mapping to ten and every other small target mapping to itself. Larger targets are divided by the digits nine down through two, always using the largest digit that still divides. The collected digits are sorted ascending and joined into the number, or the search fails when something larger than one remains.

Here's how the algorithm would work step-by-step:

  1. If the target is below ten, return ten for zero and return the target otherwise.
  2. Start from the target and walk the divisors from nine down to two.
  3. While the current product is divisible by that divisor, record the divisor and divide it out.
  4. After the divisors, if the remaining product is greater than one, return negative one.
  5. Sort the recorded digits from smallest to largest.
  6. Join them into a decimal number and return it.

Code Implementation

def smallest_digit_product(target_product):
    # Handle edge cases: A single digit number is its own smallest product.
    # Product 0 is uniquely formed by 1 and 0, so the smallest number is 10.
    if target_product < 10:
        return 10 if target_product == 0 else target_product

    found_digits = []
    current_product = target_product

    # Greedily divide by largest digits first (9 down to 2) to minimize the number of digits.
    # A number with fewer digits is always smaller than a number with more digits.
    for divisor in range(9, 1, -1):
        while current_product % divisor == 0:
            found_digits.append(divisor)
            current_product //= divisor
    
    # If the product cannot be fully factored by digits 2-9, no solution exists.
    if current_product > 1:
        return -1

    # Sort the collected digits in ascending order to construct the smallest possible number.
    # For example, digits 2 and 9 should form 29, not 92.
    found_digits.sort()
    
    final_number_string = "".join(map(str, found_digits))
    return int(final_number_string)

Big(O) Analysis

Time Complexity
O(log t * log log t) – Each successful division reduces the remaining product, so the number of recorded digits is logarithmic in the target t. The eight candidate divisors are a constant set, and the failed remainder tests are charged to those successful divisions. Sorting that logarithmic list adds another log log t factor. The bound is therefore O(log t * log log t). The work does not depend on scanning every integer up to the answer.
Space Complexity
O(log t) – The digit list holds one entry per successful division. A target t splits into O(log t) single-digit factors, and sorting reuses that same list. The joined decimal text has the same length as the list. A few integer locals do not add another growing structure. Extra space is O(log t).

Edge Cases

The target product is zero
How to Handle:
Return ten, because that is the smallest positive integer whose digits multiply to zero.
The target is a digit from one through nine
How to Handle:
Return the target itself, because that one-digit number already has the desired product.
The upward scan meets a number that contains a zero digit
How to Handle:
Treat its digit product as zero and continue unless zero was the requested product.
A factor larger than nine remains after dividing by digits from nine down to two
How to Handle:
Return negative one from the factoring method, because no single digit can absorb that factor.
The factors are discovered from large digits toward small digits
How to Handle:
Sort those digits ascending before joining them so the resulting number is as small as possible.
The target cannot be written as a product of digits
How to Handle:
The upward scan does not stop, while the factoring method returns negative one.