#3345

Easy

LeetCode Problem Workspace

Smallest Divisible Digit Product I

Find the smallest number greater than or equal to n whose digit product is divisible by t.

Problem Statement

You are given two integers, n and t. Your task is to find the smallest number greater than or equal to n, such that the product of its digits is divisible by t.

For example, if n = 10 and t = 2, the digit product of 10 is 0, which is divisible by 2. Hence, the smallest number greater than or equal to 10 with this property is 10.

Examples

Example 1

Input: n = 10, t = 2

Output: 10

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

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 Approach

Brute Force Search

Start from n and iterate through each successive number. For each number, compute the product of its digits. If the product is divisible by t, return that number. This approach checks at most 10 numbers, making it efficient given the constraints.

Digit Product Calculation

For each number, extract its digits and compute their product. If any of the digits is zero, the product is automatically zero, which is divisible by any t.

Optimization Consideration

Although the brute force approach is feasible due to the small range of numbers, consider more sophisticated checks if the range were larger. However, for this problem, simply checking each number works within the time limits.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

The time complexity depends on how many numbers are checked, but in the worst case, only 10 numbers are checked, making this approach run in constant time. The space complexity is also constant since we only store a few variables.

What Interviewers Usually Probe

Can the candidate explain their reasoning behind choosing a brute force solution?
Does the candidate optimize the search process when possible?
Is the candidate able to identify edge cases like numbers with zero as a digit?

Common Pitfalls or Variants

Common pitfalls

Failing to correctly compute the product of the digits, especially when digits contain zero.
Overcomplicating the solution instead of using a straightforward brute force approach.
Not checking enough numbers or missing edge cases where digit products are automatically divisible (e.g., numbers containing zero).

Follow-up variants

What if t is larger than any possible digit product?
How would the solution change if the range of n was significantly larger?
Can you optimize the digit product calculation to avoid redundant work?

FAQ

What is the time complexity of this problem?

The time complexity is constant, as you only check at most 10 numbers.

How can I optimize the solution for larger values of n?

For this problem, optimization is unnecessary due to the small range of n, but for larger ranges, consider avoiding redundant checks or skipping numbers with non-divisible digit products.

What happens if a number contains a zero in its digits?

If a number contains zero as a digit, its digit product will automatically be zero, which is divisible by any t.

How do I handle the case where the digit product is not divisible by t?

In that case, continue searching for the next number until you find one where the product is divisible by t.

Can I use this approach for other types of digit product problems?

Yes, this enumeration approach can be used for various digit product problems, but consider optimizing the product calculation if the range is large.

terminal

Solution

Solution 1: Enumeration

We note that within every $10$ numbers, there will definitely be an integer whose digit product is $0$. Therefore, we can directly enumerate integers greater than or equal to $n$ until we find an integer whose digit product is divisible by $t$.

1

2

3

4

5

6

7

8

9

10

class Solution:
    def smallestNumber(self, n: int, t: int) -> int:
        for i in count(n):
            p = 1
            x = i
            while x:
                p *= x % 10
                x //= 10
            if p % t == 0:
                return i

Continue Practicing

#3380 maximum area rectangle with point constraints i #3404 count special subsequences #3411 maximum subarray with equal products