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 <= 1001 <= t <= 10When 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:
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:
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 += 1Targets 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:
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)| Case | How to Handle |
|---|---|
| The target product is zero | Return ten, because that is the smallest positive integer whose digits multiply to zero. |
| The target is a digit from one through nine | 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 | 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 | 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 | 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 | The upward scan does not stop, while the factoring method returns negative one. |