Smallest Divisible Digit Product I
Asked at Microsoft
Problem
Given an integer n, find the smallest positive integer such that the product of its digits is divisible by n. Return this integer.
Asked At
| Company | Difficulty | |
|---|---|---|
| Microsoft | EASY | View all Microsoft questions → |
How to Think About It
Brute force: start from 1 and check each integer until you find one whose digit product is divisible by n.
Enumerate all single-digit numbers first; if any digit is divisible by n, return it.
For two-digit numbers, try all combinations where the product of digits is divisible by n.
Use early termination: if n is 1, return 1 immediately.
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.
What Trips People Up in Real Interviews
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.
Solution Code
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 numFrequently 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 is described in detail above, including step-by-step walkthroughs, complexity analysis, and solution code in Python. Scroll up to the "Optimal Approach" section.
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.