Smallest Divisible Digit Product I solution and explanation
3 more videos on this problem
3345. Smallest Divisible Digit Product I || C++ solution || LeetcodeCodeQuest · 2:42 · 197 views
3345. Smallest Divisible Digit Product I (Leetcode Easy)Programming Live with Larry · 4:07 · 158 views
LEETCODE || 3345.Smallest Divisible Digit Product I || PYTHONLEARN WITH ME · 3:23 · 37 views
Leetcode 3345 Smallest Divisible Digit Product IAlgorithmicIQ · 8:10 · 23 views
The problem
You are given two integers n and t. Return the smallest number greater than or equal to n such that the product of its digits is divisible by t.
Example 1:
Input: n = 10, t = 2
Output: 10
Explanation:
The digit product of 10 is 0, which is divisible by 2, making it the smallest number greater than or equal to 10 that satisfies the condition.
Example 2:
Input: n = 15, t = 3
Output: 16
Explanation:
The digit product of 16 is 6, which is divisible by 3, making it the smallest number greater than or equal to 15 that satisfies the condition.
Constraints:
1 <= n <= 1001 <= t <= 10
Approach overview
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.
Approach 1: Brute Force Approach
This approach involves iterating through each number starting from n and calculating the product of its digits. If the product is divisible by t, then that number is returned as the answer. This is the straightforward solution and can be implemented efficiently given the constraints of the problem.
def digit_product(num):
product = 1
while num > 0:
digit = num % 10
product *= digit
num //= 10
return product
def smallest_number(n, t):
i = n
while True:
if digit_product(i) % t == 0:
return i
i += 1
n, t = 15, 3
print(smallest_number(n, t))public class Main {
public static int digitProduct(int num) {
int product = 1;
while (num > 0) {
int digit = num % 10;
product *= digit;
num /= 10;
}
return product;
}
public static int smallestNumber(int n, int t) {
for (int i = n;; i++) {
if (digitProduct(i) % t == 0) {
return i;
}
}
}
public static void main(String[] args) {
int n = 15, t = 3;
System.out.println(smallestNumber(n, t));
}
}#include <iostream>
#include <string>
int digitProduct(int num) {
int product = 1;
while (num > 0) {
int digit = num % 10;
product *= digit;
num /= 10;
}
return product;
}
int smallestNumber(int n, int t) {
for (int i = n;; i++) {
if (digitProduct(i) % t == 0) {
return i;
}
}
}
int main() {
int n = 15, t = 3;
std::cout << smallestNumber(n, t) << std::endl;
return 0;
}function digitProduct(num) {
let product = 1;
while (num > 0) {
let digit = num % 10;
product *= digit;
num = Math.floor(num / 10);
}
return product;
}
function smallestNumber(n, t) {
for (let i = n;; i++) {
if (digitProduct(i) % t === 0) {
return i;
}
}
}
const n = 15, t = 3;
console.log(smallestNumber(n, t));#include <stdio.h>
int digitProduct(int num) {
int product = 1;
while (num > 0) {
int digit = num % 10;
product *= digit;
num /= 10;
}
return product;
}
int smallestNumber(int n, int t) {
for (int i = n;; i++) {
if (digitProduct(i) % t == 0) {
return i;
}
}
}
int main() {
int n = 15, t = 3;
printf("%d\n", smallestNumber(n, t));
return 0;
}using System;
class Program {
static int DigitProduct(int num) {
int product = 1;
while (num > 0) {
int digit = num % 10;
product *= digit;
num /= 10;
}
return product;
}
static int SmallestNumber(int n, int t) {
for (int i = n;; i++) {
if (DigitProduct(i) % t == 0) {
return i;
}
}
}
static void Main() {
int n = 15, t = 3;
Console.WriteLine(SmallestNumber(n, t));
}
}This Python function loops through each number starting from n and calculates the product of its digits until it finds one that is divisible by t.
Time Complexity: O(1), constrained by the limited range of n.
Space Complexity: O(1).
Approach 2: Direct Check with Early Termination
This approach checks each number starting from n and terminates early when a number with digit '0' in it is found, as its digit product will be zero and divisible by any t.
def has_zero(num):
while num > 0:
if num % 10 == 0:
return True
num //= 10
return False
def digit_product(num):
product = 1
while num > 0:
digit = num % 10
if digit == 0:
return 0
product *= digit
num //= 10
return product
def smallest_number(n, t):
i = n
while True:
if has_zero(i) or digit_product(i) % t == 0:
return i
i += 1
n, t = 15, 3
print(smallest_number(n, t))public class Main {
public static boolean hasZero(int num) {
while (num > 0) {
if (num % 10 == 0) return true;
num /= 10;
}
return false;
}
public static int digitProduct(int num) {
int product = 1;
while (num > 0) {
int digit = num % 10;
if (digit == 0) return 0;
product *= digit;
num /= 10;
}
return product;
}
public static int smallestNumber(int n, int t) {
for (int i = n;; i++) {
if (hasZero(i) || digitProduct(i) % t == 0) {
return i;
}
}
}
public static void main(String[] args) {
int n = 15, t = 3;
System.out.println(smallestNumber(n, t));
}
}#include <iostream>
bool hasZero(int num) {
while (num > 0) {
if (num % 10 == 0)
return true;
num /= 10;
}
return false;
}
int digitProduct(int num) {
int product = num % 10;
num /= 10;
while (num > 0) {
int digit = num % 10;
if (digit == 0) return 0;
product *= digit;
num /= 10;
}
return product;
}
int smallestNumber(int n, int t) {
for (int i = n;; ++i) {
if (hasZero(i) || digitProduct(i) % t == 0) {
return i;
}
}
}
int main() {
int n = 15, t = 3;
std::cout << smallestNumber(n, t) << std::endl;
return 0;
}function hasZero(num) {
while (num > 0) {
if (num % 10 === 0) return true;
num = Math.floor(num / 10);
}
return false;
}
function digitProduct(num) {
let product = 1;
while (num > 0) {
let digit = num % 10;
if (digit === 0) return 0;
product *= digit;
num = Math.floor(num / 10);
}
return product;
}
function smallestNumber(n, t) {
for (let i = n;; i++) {
if (hasZero(i) || digitProduct(i) % t === 0) {
return i;
}
}
}
const n = 15, t = 3;
console.log(smallestNumber(n, t));#include <stdio.h>
int hasZero(int num) {
while (num > 0) {
int digit = num % 10;
if (digit == 0) return 1;
num /= 10;
}
return 0;
}
int smallestNumber(int n, int t) {
for (int i = n;; i++) {
if (hasZero(i) || digitProduct(i) % t == 0) {
return i;
}
}
}
int main() {
int n = 15, t = 3;
printf("%d\n", smallestNumber(n, t));
return 0;
}using System;
class Program {
static bool HasZero(int num) {
while (num > 0) {
if (num % 10 == 0) return true;
num /= 10;
}
return false;
}
static int DigitProduct(int num) {
int product = 1;
while (num > 0) {
int digit = num % 10;
if (digit == 0) return 0;
product *= digit;
num /= 10;
}
return product;
}
static int SmallestNumber(int n, int t) {
for (int i = n;; i++) {
if (HasZero(i) || DigitProduct(i) % t == 0) {
return i;
}
}
}
static void Main() {
int n = 15, t = 3;
Console.WriteLine(SmallestNumber(n, t));
}
}The Python solution evaluates zero digits prior to computing further, allowing potential early exit.
Time Complexity: O(1), faster if zeros are found early.
Space Complexity: O(1).
Approach 3: Enumeration
We note that within every 10 numbers, there will definitely be an integer whose digit product is 0. Therefore, we can directly enumerate integers greater than or equal to n until we find an integer whose digit product is divisible by t.
The time complexity is O(log n), and the space complexity is O(1).
function smallestNumber(n: number, t: number): number {
for (let i = n; ; ++i) {
let p = 1;
for (let x = i; x; x = Math.floor(x / 10)) {
p *= x % 10;
}
if (p % t === 0) {
return i;
}
}
}func smallestNumber(n int, t int) int {
for i := n; ; i++ {
p := 1
for x := i; x > 0; x /= 10 {
p *= x % 10
}
if p%t == 0 {
return i
}
}
}Complexity comparison
| Approach | Complexity |
|---|---|
| Brute Force Approach | Time Complexity: O(1), constrained by the limited range of |
| Direct Check with Early Termination | Time Complexity: O(1), faster if zeros are found early. |
| Enumeration | – |
Complexity analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Brute Force Enumeration | O(k * d) | O(1) | Simple implementation when constraints are small and straightforward enumeration is acceptable |
| Direct Check with Early Termination | O(k * d) | O(1) | Preferred in practice to reduce unnecessary digit multiplications during checks |
Frequently asked questions
Is Smallest Divisible Digit Product I easy or hard?
Smallest Divisible Digit Product I is classified as an Easy problem on LeetCode with an acceptance rate above 60%. It mainly tests digit manipulation, basic math operations, and careful iteration with small optimizations.
Smallest Divisible Digit Product I Python/Java solution
In Python or Java, iterate from n upward and compute the product of digits using modulo and division operations. Check product % t == 0 for each candidate and return the first valid number. The implementation uses constant extra space and simple loops.
How to solve Smallest Divisible Digit Product I in O(n)?
Treat the problem as sequential enumeration starting from n. For each number, extract digits and compute the running product while checking divisibility by t. Stop early if the product becomes divisible by t or if a zero digit appears, which guarantees divisibility.
What is the best approach for Smallest Divisible Digit Product I?
Enumeration with early termination is the most practical approach. Start from n and check each number’s digit product, but stop computing the product as soon as it becomes divisible by t or a zero digit appears. This keeps the logic simple while avoiding unnecessary multiplications.
Is Smallest Divisible Digit Product I asked at Google/Amazon/Meta?
The problem itself is from LeetCode and categorized as Easy, focusing on digit manipulation and enumeration. Similar digit-product or digit-processing questions appear in interviews at large tech companies because they test number handling and basic algorithmic reasoning.
What data structure is used in Smallest Divisible Digit Product I?
No complex data structure is required. The solution relies on integer arithmetic, digit extraction using modulo and division, and simple iteration. The problem mainly falls under math and enumeration techniques.
What is the time complexity of Smallest Divisible Digit Product I?
The time complexity is O(k * d), where k is the number of integers checked starting from n and d is the number of digits in each number. Each candidate requires scanning its digits to compute the product. Space complexity is O(1) since only a few variables are used.