EasyMathEnumerationUpdated Sep 2026

3345. Smallest Divisible Digit Product I

Asked at Microsoft

Difficulty

Easy

Time

O(k * d)

Space

O(1)

Pattern

Math

Companies

1

Problem

You are given two integers, n and t. Find the smallest integer x such that x >= n and the product of the digits of x is divisible by t.

To get the digit product, multiply every digit of the number together. For example, the digit product of 16 is 1 * 6 = 6. A number is a valid answer when that product can be divided by t with no remainder.

If several numbers work, return the smallest one. Note that any number containing the digit 0 has a digit product of 0, and 0 is divisible by every t, so such numbers always qualify.

Check numbers from n upward

candidates15161715 fails (5 not divisible by 3), 16 works (6 isdivisible by 3)t = 315 → 1*5 = 5 ✗16 → 1*6 = 6 ✓
We start at n and keep going until the digit product is divisible by t.

Constraints

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

Examples

Example 1
Inputn = 10, t = 2
Output10
WhyThe digit product of 10 is 1 * 0 = 0. Zero is divisible by 2, so 10 already works and it is the smallest number that is at least 10.
Example 2
Inputn = 15, t = 3
Output16
Why15 has digit product 1 * 5 = 5, and 5 is not divisible by 3. The next number, 16, has digit product 1 * 6 = 6, and 6 is divisible by 3. So 16 is the answer.

Asked At

1 companies
CompanyDifficulty
MicrosoftEasyView all Microsoft questions →

How to Think About It

1

Brute force: start from 1 and check each integer until you find one whose digit product is divisible by n.

2

Enumerate all single-digit numbers first; if any digit is divisible by n, return it.

3

For two-digit numbers, try all combinations where the product of digits is divisible by n.

4

Use early termination: if n is 1, return 1 immediately.

5

Optimal: enumerate candidates in increasing order, computing digit product on the fly, and return the first match.

Optimal Approach

Iterate through all positive integers starting from 1. For each candidate, compute the product of its digits. If the product is divisible by n, return the candidate. Since n is small (typically <= 100), the answer is guaranteed to be found quickly. Single-digit numbers should be checked first, then two-digit numbers, and so on.

Try each number and multiply its digits

start at x = nproduct = 1multiply each digitproduct % t == 0 ?yes → return x, no → x + 1The first candidate that passes the test is thesmallest valid answer.x = 15: 1*5 = 5, 5 % 3 != 0x = 16: 1*6 = 6, 6 % 3 == 0return 16
For every candidate we peel off digits with % 10 and // 10, then test the product against t.
ComplexityTime O(k * d)Space O(1)k is how many candidates we test before the first match and d is the number of digits per candidate; the search is very short because n <= 100.

What Trips People Up in Real Interviews

1

Clarify constraints on n — typically small values make brute force acceptable.

2

Remember that single-digit numbers (1-9) should be checked before multi-digit.

3

If n itself is a single digit, the answer might be n itself.

4

Edge case: n = 1, the answer is 1 since any number with product 1 works.

5

Do not overcomplicate — simple enumeration with digit product calculation is sufficient.

Solution Code

O(k * d) time
def smallestNumber(n):
    for num in range(1, 100000):
        product = 1
        temp = num
        while temp > 0:
            product *= temp % 10
            temp //= 10
        if product % n == 0:
            return num

Pro at DSA?

Test your skills with a real FAANG-style mock interview.

Start a Mock Interview →

Frequently Asked Questions

What is the Smallest Divisible Digit Product I problem?

Given an integer n, find the smallest positive integer such that the product of its digits is divisible by n. Return this integer.

How do you solve Smallest Divisible Digit Product I?

The optimal approach runs in O(k * d) time and O(1) space. Scroll up to "Optimal Approach" for the step-by-step walkthrough, diagrams, and code in Python, C++ and Java.

What companies ask Smallest Divisible Digit Product I?

Smallest Divisible Digit Product I is asked at Microsoft. It is a easy difficulty problem.

What are common mistakes on Smallest Divisible Digit Product I?
  • Clarify constraints on n — typically small values make brute force acceptable.
  • Remember that single-digit numbers (1-9) should be checked before multi-digit.
  • If n itself is a single digit, the answer might be n itself.
  • Edge case: n = 1, the answer is 1 since any number with product 1 works.
  • Do not overcomplicate — simple enumeration with digit product calculation is sufficient.