Smallest Divisible Digit Product I - Video Solutions

Problem Overview: Given integers n and t, return the smallest integer greater than or equal to n such that the product of its digits is divisible by t. The task is essentially checking numbers sequentially and verifying whether their digit product satisfies the divisibility condition.

Approach 1: Brute Force Enumeration (O(k * d) time, O(1) space)

Start from n and increment the number one by one until a valid candidate is found. For each number, compute the product of its digits by repeatedly extracting digits using modulo and division operations. After computing the product, check whether product % t == 0. If true, return that number immediately. Each check processes d digits where d is the number of digits, and k represents how many numbers you test before finding a valid one.

This method relies on simple iteration and digit manipulation, making it straightforward to implement. It works well because the constraints are small enough that the search typically terminates quickly. The approach mainly uses basic math operations and simple enumeration of candidates.

Approach 2: Direct Check with Early Termination (O(k * d) time, O(1) space)

This optimization keeps the same enumeration idea but improves how the digit product is computed. While multiplying digits, continuously check divisibility against t. If the intermediate product already becomes divisible by t, further digit processing is unnecessary and you can stop early. Another useful observation: if a digit 0 appears, the entire product becomes zero, which is divisible by any positive t, so the number immediately qualifies.

During digit extraction, update the running product and apply early termination rules whenever possible. This avoids multiplying all digits for many candidates, especially when numbers contain zero or when the product quickly reaches a multiple of t. The algorithm still scans numbers sequentially, but each check often finishes faster in practice.

Recommended for interviews: Start with the brute force explanation to show you understand the direct interpretation of the problem. Then mention the early-termination optimization while computing the digit product. Interviewers typically expect this improvement because it reduces unnecessary work while keeping the implementation simple and constant-space.