LeetCode 3345 - Smallest Divisible Digit Product I

The problem gives us two integers, n and t. We must find the smallest integer greater than or equal to n whose digit product is divisible by t. The digit product of a number is obtained by multiplying all of its digits together.

leetcodeeasymathenumeration

LeetCode Problem 3345

Difficulty: 🟢 Easy
Topics: Math, Enumeration

Solution

Problem Understanding

The problem gives us two integers, n and t. We must find the smallest integer greater than or equal to n whose digit product is divisible by t.

The digit product of a number is obtained by multiplying all of its digits together. For example:

  • The digit product of 16 is 1 × 6 = 6
  • The digit product of 203 is 2 × 0 × 3 = 0

A number satisfies the condition if:

$$\text{digit product} \bmod t = 0$$

The goal is not to find any valid number, but specifically the smallest valid number greater than or equal to n.

The constraints are very small:

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

These constraints immediately suggest that brute force enumeration is feasible. Since the search space is tiny, we can simply test numbers one by one until we find a valid answer.

One especially important observation is that any number containing the digit 0 automatically has digit product 0. Since 0 is divisible by every positive integer, such numbers are always valid regardless of t.

There are several edge cases worth considering:

  • Numbers containing 0, because their digit product becomes 0
  • t = 1, because every integer is divisible by 1
  • Single digit numbers
  • Numbers where the first valid answer is several increments away
  • Numbers whose digit product becomes large, although this is harmless because the input range is tiny

The problem guarantees that inputs are positive integers, so we do not need to handle negative values or empty digit sequences.

Approaches

Brute Force Approach

The brute force approach starts at n and checks every number one by one.

For each candidate number:

  1. Extract its digits
  2. Compute the product of those digits
  3. Check whether the product is divisible by t
  4. If yes, return the number
  5. Otherwise continue searching

This works because we examine numbers in increasing order. The first valid number we encounter must therefore be the smallest valid answer.

Although brute force can sometimes be too slow, the constraints here are extremely small. Even in the worst case, we only check a small number of integers before finding a valid one.

Key Insight

The key insight is that the constraints are tiny enough that optimization is unnecessary.

Instead of attempting digit dynamic programming, factorization tricks, or mathematical pruning, we can directly simulate the process.

The digit product operation itself is also very cheap because numbers are at most a few digits long.

This makes the straightforward enumeration solution both simple and optimal for the given constraints.

Approach Time Complexity Space Complexity Notes
Brute Force O(k × d) O(1) Checks each number sequentially and computes digit product
Optimal O(k × d) O(1) Same as brute force because constraints are tiny

Here:

  • k is the number of integers checked before finding the answer
  • d is the number of digits in the current number

Since n <= 100, both values are extremely small.

Algorithm Walkthrough

  1. Start with the candidate number equal to n.
  2. For the current candidate, compute the product of its digits.

We repeatedly extract digits using modulo and integer division:

  • digit = number % 10
  • number //= 10

Multiply all extracted digits together to get the digit product. 3. After computing the digit product, check whether:

$$\text{product} \bmod t = 0$$

If this condition is true, we have found a valid answer. 4. Return the current candidate immediately.

Since we are checking numbers in increasing order, the first valid number is guaranteed to be the smallest valid solution. 5. Otherwise increment the candidate by 1 and repeat the process.

Why it works

The algorithm checks every integer greater than or equal to n in strictly increasing order. For each number, it correctly computes the digit product and verifies divisibility by t.

Because no smaller unchecked number exists before the returned value, the first valid number found must be the smallest valid answer.

Python Solution

class Solution:
    def smallestNumber(self, n: int, t: int) -> int:
        def digit_product(num: int) -> int:
            product = 1
            
            while num > 0:
                product *= num % 10
                num //= 10
            
            return product
        
        current = n
        
        while True:
            if digit_product(current) % t == 0:
                return current
            
            current += 1

The implementation follows the algorithm directly.

The helper function digit_product computes the product of all digits in a number. It repeatedly extracts the last digit using % 10 and removes it using integer division // 10.

The main loop starts from n and continuously checks each candidate number.

For every candidate:

  • Compute its digit product
  • Check divisibility by t
  • Return immediately if valid

Otherwise the candidate is incremented and the search continues.

Because the constraints are very small, this implementation is both efficient and easy to understand.

Go Solution

func smallestNumber(n int, t int) int {
	digitProduct := func(num int) int {
		product := 1

		for num > 0 {
			product *= num % 10
			num /= 10
		}

		return product
	}

	current := n

	for {
		if digitProduct(current)%t == 0 {
			return current
		}

		current++
	}
}

The Go implementation mirrors the Python version closely.

A local helper function computes the digit product by repeatedly extracting digits.

The infinite for loop continuously checks increasing numbers until a valid answer is found.

Since the constraints are tiny, integer overflow is not a concern in this problem.

Worked Examples

Example 1

Input:

n = 10
t = 2

We begin checking from 10.

Current Number Digits Digit Product Product % 2 Valid?
10 1, 0 0 0 Yes

Since 0 % 2 = 0, the number 10 satisfies the condition immediately.

Output:

10

Example 2

Input:

n = 15
t = 3

We begin checking from 15.

Current Number Digits Digit Product Product % 3 Valid?
15 1, 5 5 2 No
16 1, 6 6 0 Yes

The first valid number encountered is 16.

Output:

16

Complexity Analysis

Measure Complexity Explanation
Time O(k × d) We may check k numbers, each requiring processing of d digits
Space O(1) Only constant extra variables are used

The algorithm uses constant auxiliary space because it stores only a few integer variables.

The runtime depends on how many numbers must be checked before finding a valid answer. Each check processes the digits of the number once.

Given the tiny constraints, the actual runtime is extremely small.

Test Cases

solution = Solution()

assert solution.smallestNumber(10, 2) == 10  # contains zero, product is 0
assert solution.smallestNumber(15, 3) == 16  # next valid number
assert solution.smallestNumber(1, 1) == 1    # every number divisible by 1
assert solution.smallestNumber(7, 7) == 7    # single digit already valid
assert solution.smallestNumber(8, 9) == 9    # must increment
assert solution.smallestNumber(19, 2) == 20  # zero digit makes product 0
assert solution.smallestNumber(99, 10) == 100  # requires moving to next digit length
assert solution.smallestNumber(25, 5) == 25  # already divisible
assert solution.smallestNumber(26, 5) == 30  # next valid number includes zero
assert solution.smallestNumber(100, 3) == 100  # zero product always divisible
Test Why
n=10, t=2 Validates zero digit behavior
n=15, t=3 Matches provided example
n=1, t=1 Smallest possible inputs
n=7, t=7 Single digit already valid
n=8, t=9 Requires incrementing search
n=19, t=2 Transition to a number containing zero
n=99, t=10 Expands into three digits
n=25, t=5 Already satisfies condition
n=26, t=5 Requires several checks
n=100, t=3 Multiple zeros in number

Edge Cases

One important edge case occurs when the number contains a 0. Any digit product involving zero immediately becomes 0, and 0 is divisible by every positive integer. A buggy implementation might incorrectly treat 0 as invalid or accidentally skip such numbers. This implementation naturally handles the case because the digit multiplication correctly produces 0.

Another important case is t = 1. Every integer is divisible by 1, so the answer should always be n. Some implementations unnecessarily continue searching instead of immediately recognizing that every digit product satisfies the condition. In this solution, the divisibility check naturally succeeds on the first iteration.

A third edge case involves crossing digit boundaries, such as moving from 99 to 100. The digit count changes, and the presence of zeros dramatically changes the digit product. Incorrect digit extraction logic can fail in these transitions. The implementation correctly processes every digit independently, so numbers with different digit lengths work without any special handling.