3345. Smallest Divisible Digit Product I
Problem Description
You need to find the smallest number that meets two conditions:
- It must be greater than or equal to a given number
n
- The product of its digits must be divisible by a given number
t
For example, if n = 10
and t = 2
, you would check numbers starting from 10:
- For 10: digit product = 1 × 0 = 0, and 0 is divisible by 2, so the answer is 10
- If
n = 15
andt = 3
, you would check:- 15: digit product = 1 × 5 = 5, not divisible by 3
- 16: digit product = 1 × 6 = 6, divisible by 3, so the answer is 16
The solution works by checking each number starting from n
and calculating the product of its digits. For each number, it extracts digits one by one using modulo 10 operation (x % 10
) and integer division (x // 10
), multiplying them together. Once it finds a number whose digit product is divisible by t
(checked using p % t == 0
), it returns that number.
The key insight is that you don't need to check too many numbers because within any consecutive 10 numbers, at least one will contain the digit 0, making its digit product 0, which is divisible by any non-zero t
.
Intuition
The key observation is that we're looking for a number whose digit product is divisible by t
. Since we want the smallest such number that's at least n
, the natural approach is to start from n
and check each consecutive number.
Why can we use brute force enumeration? The critical insight is that we won't need to check many numbers. Consider any sequence of 10 consecutive integers - at least one of them will contain the digit 0
. For example, in the range [20, 29]
, the number 20
has a 0
. When any number contains a 0
digit, the product of all its digits becomes 0
, and 0
is divisible by any non-zero integer t
.
This means in the worst case, we only need to check at most 10 numbers before finding one that works. Even if we start at a number like 11
where the digit product is 1 × 1 = 1
(not divisible by most values of t
), by the time we reach 20
, we'll have a digit product of 2 × 0 = 0
which satisfies our condition.
Therefore, instead of trying to construct the answer digit by digit or using complex mathematical formulas, we can simply iterate through numbers starting from n
, calculate each number's digit product, and return the first one that's divisible by t
. The efficiency is guaranteed by the fact that zeros appear frequently in decimal representations.
Learn more about Math patterns.
Solution Approach
The solution uses a straightforward enumeration approach. We iterate through integers starting from n
and check each one until we find a number whose digit product is divisible by t
.
The implementation follows these steps:
-
Start enumeration from n: Use
count(n)
to generate consecutive integers starting fromn
. This creates an infinite iterator that yieldsn, n+1, n+2, ...
-
Calculate digit product for each number: For each number
i
in the sequence:- Initialize a product variable
p = 1
- Create a copy of the current number
x = i
- Extract digits using a while loop:
- Get the last digit using
x % 10
- Multiply it with the running product:
p *= x % 10
- Remove the last digit using integer division:
x //= 10
- Continue until all digits are processed (when
x
becomes 0)
- Get the last digit using
- Initialize a product variable
-
Check divisibility: After calculating the digit product
p
, check ifp % t == 0
. If true, we've found our answer and returni
. -
Return the first valid number: The loop continues until it finds the first number whose digit product is divisible by
t
, which is guaranteed to happen within at most 10 iterations due to the presence of zeros in decimal representations.
For example, with n = 23
and t = 6
:
- Check 23: digits are 2 and 3, product =
2 × 3 = 6
,6 % 6 = 0
✓ Return 23 - If it wasn't divisible, we'd check 24, 25, ..., until finding a valid number
The time complexity is O(d) per number checked, where d is the number of digits, and we check at most 10 numbers, making it very efficient.
Ready to land your dream job?
Unlock your dream job with a 5-minute evaluator for a personalized learning plan!
Start EvaluatorExample Walkthrough
Let's walk through finding the smallest number ≥ n = 234
with digit product divisible by t = 7
.
Step 1: Check n = 234
- Extract digits: 234 → 4 (234 % 10), then 3 (23 % 10), then 2 (2 % 10)
- Calculate product: 2 × 3 × 4 = 24
- Check divisibility: 24 % 7 = 3 (not divisible by 7)
- Continue to next number
Step 2: Check 235
- Extract digits: 235 → 5, 3, 2
- Calculate product: 2 × 3 × 5 = 30
- Check divisibility: 30 % 7 = 2 (not divisible by 7)
- Continue to next number
Step 3: Check 236
- Extract digits: 236 → 6, 3, 2
- Calculate product: 2 × 3 × 6 = 36
- Check divisibility: 36 % 7 = 1 (not divisible by 7)
- Continue to next number
Step 4: Check 237
- Extract digits: 237 → 7, 3, 2
- Calculate product: 2 × 3 × 7 = 42
- Check divisibility: 42 % 7 = 0 ✓ (divisible by 7!)
- Return 237
The algorithm found the answer after checking only 4 numbers. Note that if we hadn't found a match yet, by the time we reached 240, its digit product would be 2 × 4 × 0 = 0, which is divisible by any non-zero t, guaranteeing we find an answer within 10 iterations.
Solution Implementation
1class Solution:
2 def smallestNumber(self, n: int, t: int) -> int:
3 """
4 Find the smallest number >= n whose digit product is divisible by t.
5
6 Args:
7 n: The starting number (minimum value to consider)
8 t: The target divisor for the digit product
9
10 Returns:
11 The smallest number >= n whose digit product is divisible by t
12 """
13 from itertools import count
14
15 # Iterate through all numbers starting from n
16 for candidate in count(n):
17 # Calculate the product of all digits
18 digit_product = 1
19 temp_num = candidate
20
21 # Extract each digit and multiply them together
22 while temp_num > 0:
23 digit = temp_num % 10 # Get the last digit
24 digit_product *= digit # Multiply it to the product
25 temp_num //= 10 # Remove the last digit
26
27 # Check if the digit product is divisible by t
28 if digit_product % t == 0:
29 return candidate
30
1class Solution {
2 /**
3 * Finds the smallest number greater than or equal to n whose digit product is divisible by t
4 * @param n the minimum number to start searching from
5 * @param t the target divisor for the digit product
6 * @return the smallest number >= n whose digit product is divisible by t
7 */
8 public int smallestNumber(int n, int t) {
9 // Iterate from n onwards until we find a valid number
10 for (int currentNumber = n; ; currentNumber++) {
11 // Calculate the product of all digits in currentNumber
12 int digitProduct = 1;
13 int tempNumber = currentNumber;
14
15 // Extract each digit and multiply them together
16 while (tempNumber > 0) {
17 int lastDigit = tempNumber % 10; // Get the last digit
18 digitProduct *= lastDigit; // Multiply to the product
19 tempNumber /= 10; // Remove the last digit
20 }
21
22 // Check if the digit product is divisible by t
23 if (digitProduct % t == 0) {
24 return currentNumber;
25 }
26 }
27 }
28}
29
1class Solution {
2public:
3 int smallestNumber(int n, int t) {
4 // Iterate from n onwards to find the smallest valid number
5 for (int current = n; ; ++current) {
6 // Calculate the product of all digits in the current number
7 int digitProduct = 1;
8 int temp = current;
9
10 // Extract each digit and multiply them together
11 while (temp > 0) {
12 int digit = temp % 10; // Get the last digit
13 digitProduct *= digit; // Multiply to the product
14 temp /= 10; // Remove the last digit
15 }
16
17 // Check if the product of digits is divisible by t
18 if (digitProduct % t == 0) {
19 return current; // Found the smallest number that satisfies the condition
20 }
21 }
22 }
23};
24
1/**
2 * Finds the smallest number greater than or equal to n whose digit product is divisible by t
3 * @param n - The starting number to search from
4 * @param t - The target divisor for the digit product
5 * @returns The smallest number >= n whose digit product is divisible by t
6 */
7function smallestNumber(n: number, t: number): number {
8 // Iterate from n onwards until we find a valid number
9 for (let currentNumber = n; ; currentNumber++) {
10 // Calculate the product of all digits in currentNumber
11 let digitProduct = 1;
12 let tempNumber = currentNumber;
13
14 // Extract each digit and multiply them together
15 while (tempNumber > 0) {
16 const lastDigit = tempNumber % 10;
17 digitProduct *= lastDigit;
18 tempNumber = Math.floor(tempNumber / 10);
19 }
20
21 // Check if the digit product is divisible by t
22 if (digitProduct % t === 0) {
23 return currentNumber;
24 }
25 }
26}
27
Time and Space Complexity
The time complexity is O(t * log n)
where n
is the starting number and t
is the target divisor. The algorithm iterates through numbers starting from n
until it finds one whose digit product is divisible by t
. In the worst case, we need to check up to t
numbers (since at most every t
-th number could have a digit product divisible by t
). For each number checked, we calculate the product of its digits, which takes O(log n)
time (the number of digits in the number). Therefore, the overall time complexity is O(t * log n)
.
The space complexity is O(1)
as we only use a constant amount of extra space for variables i
, p
, and x
, regardless of the input size.
Note: The reference answer states O(log n)
for time complexity, which appears to consider only the digit product calculation for a single number, not accounting for the iteration through potentially multiple numbers until finding one that satisfies the condition.
Learn more about how to find time and space complexity quickly.
Common Pitfalls
1. Not Handling Zero Digits Properly
The most critical pitfall is forgetting that when a number contains the digit 0, the entire product becomes 0. This is actually beneficial since 0 is divisible by any non-zero number, but failing to recognize this can lead to unnecessary complexity or incorrect edge case handling.
Problem Example:
# Incorrect approach that might skip numbers with 0
def incorrect_solution(n, t):
for candidate in count(n):
if '0' in str(candidate): # Wrong: skipping zeros
continue
# ... calculate product
Solution: Embrace zeros as valid solutions. When the digit product is 0, it's divisible by any non-zero t.
2. Integer Overflow in Large Digit Products
For numbers with many large digits, the product can grow extremely large, potentially causing overflow issues in languages with fixed integer sizes (though Python handles arbitrary precision).
Problem Example:
# For n = 9999999 and t = 2 # Digit product = 9^7 = 4,782,969 (very large)
Solution: Consider early termination when a 0 is encountered, or use modular arithmetic:
def optimized_solution(n, t):
for candidate in count(n):
digit_product = 1
temp_num = candidate
while temp_num > 0:
digit = temp_num % 10
if digit == 0: # Early termination
digit_product = 0
break
digit_product = (digit_product * digit) % t # Keep product modulo t
temp_num //= 10
if digit_product % t == 0:
return candidate
3. Inefficient String Conversion Approach
Converting numbers to strings to extract digits is less efficient than using arithmetic operations.
Problem Example:
# Inefficient approach
def string_based_solution(n, t):
for candidate in count(n):
digits = [int(d) for d in str(candidate)] # String conversion overhead
product = 1
for digit in digits:
product *= digit
Solution: Stick with the arithmetic approach using modulo and integer division as shown in the original solution.
4. Not Considering t = 1 Edge Case
When t = 1, every number's digit product is divisible by 1, so the answer is always n itself. While the general solution handles this correctly, recognizing this case can lead to immediate optimization.
Solution: Add a special case check:
def optimized_solution(n, t):
if t == 1:
return n # Every digit product is divisible by 1
# ... rest of the solution
5. Misunderstanding the Problem Requirements
Some might mistakenly think they need to find a number whose digits sum (not product) is divisible by t, or that the number itself (not its digit product) should be divisible by t.
Solution: Carefully read the problem - we need the PRODUCT of digits to be divisible by t, not the sum or the number itself.
Which algorithm should you use to find a node that is close to the root of the tree?
Recommended Readings
Math for Technical Interviews How much math do I need to know for technical interviews The short answer is about high school level math Computer science is often associated with math and some universities even place their computer science department under the math faculty However the reality is that you
Coding Interview Patterns Your Personal Dijkstra's Algorithm to Landing Your Dream Job The goal of AlgoMonster is to help you get a job in the shortest amount of time possible in a data driven way We compiled datasets of tech interview problems and broke them down by patterns This way
Recursion Recursion is one of the most important concepts in computer science Simply speaking recursion is the process of a function calling itself Using a real life analogy imagine a scenario where you invite your friends to lunch https assets algo monster recursion jpg You first call Ben and ask
Want a Structured Path to Master System Design Too? Don’t Miss This!