Smallest Divisible Digit Product I - Practice Coding Problems

Smallest Divisible Digit Product I - Problem

Math Enumeration Easy

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.

For example, if n = 15 and t = 3, we need to find the smallest number ≥ 15 where the product of digits is divisible by 3. The number 16 has digit product 1×6 = 6, which is divisible by 3, so the answer is 16.

Input & Output

Example 1 — Basic Case

$ Input: n = 15, t = 3

› Output: 16

💡 Note: Starting from 15: digit product = 1×5 = 5, not divisible by 3. Next number 16: digit product = 1×6 = 6, which is divisible by 3, so return 16.

Example 2 — Zero Digit

$ Input: n = 19, t = 7

› Output: 20

💡 Note: Starting from 19: digit product = 1×9 = 9, not divisible by 7. Next number 20: digit product = 2×0 = 0, which is divisible by 7, so return 20.

Example 3 — Answer is n itself

$ Input: n = 12, t = 2

› Output: 12

💡 Note: Starting from 12: digit product = 1×2 = 2, which is divisible by 2, so return 12 itself.

Constraints

1 ≤ n ≤ 10⁶
1 ≤ t ≤ 10⁶

Visualization

Tap to expand

Understanding the Visualization

Input

Given n=15, t=3, find smallest number ≥ 15

Process

Check digit products: 15→5, 16→6

Output

Return 16 (first with digit product divisible by 3)

Key Takeaway

🎯 Key Insight: Iterate from n upwards checking digit products until finding one divisible by t

Asked in

G Google 25 M Microsoft 15

The key insight is to iterate from n upwards and check each number's digit product for divisibility by t. The brute force approach works well for this problem since the search space is typically small. Best approach is brute force enumeration. Time: O(k×d), Space: O(1)

Common Approaches

Approach	Time	Space	Notes
✓ Early Termination Optimization	O(k × d)	O(1)	Same approach but with early exit when digit product becomes 0
Brute Force Enumeration	O(k × d)	O(1)	Check every number starting from n until digit product is divisible by t

Early Termination Optimization — Algorithm Steps

Step 1: Start with current number = n
Step 2: Calculate product of digits, exit early if any digit is 0 and t ≠ 0
Step 3: Check if product is divisible by t
Step 4: Return if found, otherwise increment and repeat

Visualization

Tap to expand

Step-by-Step Walkthrough

Check n=19

Start from given number

Find zero digit

20: contains 0, so digit product = 0

Early return

0 is divisible by any non-zero t

Code -

solution.c — C

#include <stdio.h>
#include <stdbool.h>

int solution(int n, int t) {
    int current = n;
    while (1) {
        // Calculate product of digits
        int product = 1;
        int temp = current;
        bool hasZero = false;
        
        while (temp > 0) {
            int digit = temp % 10;
            if (digit == 0) {
                hasZero = true;
                product = 0;
                break;
            }
            product *= digit;
            temp /= 10;
        }
        
        // Check if divisible by t
        if (hasZero && t != 0) {
            return current;  // 0 is divisible by any non-zero number
        } else if (!hasZero && product % t == 0) {
            return current;
        }
        
        current++;
    }
}

int main() {
    int n, t;
    scanf("%d", &n);
    scanf("%d", &t);
    int result = solution(n, t);
    printf("%d\n", result);
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(k × d)

k is the gap between n and answer, d is average number of digits

✓ Linear Growth

Space Complexity

O(1)

Only using constant extra variables

✓ Linear Space

12.0K Views

Medium Frequency

~15 min Avg. Time

450 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Early Termination Optimization — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler