Smallest Divisible Digit Product I

Difficulty: Easy | Acceptance: 64.40% | Paid: No Topics: Math, Enumeration

You are given two integers n and k.

Return the smallest positive integer x such that:

x has exactly n digits. The product of the digits of x is divisible by k. If no such integer exists, return -1.

• Examples
• Constraints
• Mathematical Logic
• Brute Force Enumeration

Examples

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 <= 9
1 <= k <= 100

Mathematical Logic

Intuition The key observation is that for any number with more than 1 digit, the smallest possible number is 10^(n-1) (e.g., 10, 100, 1000). This number always contains at least one zero. The product of digits including a zero is 0. Since 0 is divisible by any non-zero integer $k$, the answer for any $n > 1$ is simply 10^(n-1). For $n=1$, we must check digits 1 through 9 manually.

Steps

• If $n > 1$, return 10^(n-1).
• If $n == 1$, iterate through digits $d$ from 1 to 9.
• If $d % k == 0$, return $d$.
• If the loop finishes without finding a match, return -1.

class Solution:
    def smallestNumber(self, n: int, k: int) -> int:
        if n > 1:
            return 10 ** (n - 1)
        for i in range(1, 10):
            if i % k == 0:
                return i
        return -1

Complexity

• Time: O(1) - We perform at most 9 iterations for $n=1$, or a constant time calculation for $n>1$.
• Space: O(1) - No extra space is used.
• Notes: This is the optimal solution.

Brute Force Enumeration

Intuition We can iterate through all n-digit numbers starting from the smallest (10^(n-1)) and check if the product of their digits is divisible by k. The first number we find is the answer.

Steps

• Calculate the start range as 10^(n-1) and end range as 10^n - 1.
• Iterate $x$ from start to end.
• For each $x$, calculate the product of its digits.
• If product $% k == 0$, return $x$.
• If the loop finishes, return -1.

class Solution:
    def smallestNumber(self, n: int, k: int) -> int:
        start = 10 ** (n - 1)
        end = 10 ** n
        for x in range(start, end):
            prod = 1
            temp = x
            while temp > 0:
                prod *= temp % 10
                temp //= 10
            if prod % k == 0:
                return x
        return -1

Complexity

• Time: O(9 * 10ⁿ) - In the worst case, we iterate through all $n$-digit numbers. For $n=9$, this is very slow.
• Space: O(1) - Constant space.
• Notes: This approach is conceptually simple but inefficient for larger values of $n$ compared to the mathematical approach.