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.

Examples

Example 1

1
2
3
4
5
6
7
8
9


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

1
2
3
4
5
6
7
8
9


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 <= 100
  • 1 <= t <= 10

Solution

Method 1 – Brute Force Enumeration

Intuition

Since n and t are small, we can simply check each number starting from n, compute the product of its digits, and return the first number whose product is divisible by t.

Approach

  1. For each integer x from n upwards:
    • Compute the product of its digits.
    • If the product is divisible by t, return x.
  2. (Since n <= 100 and t <= 10, this is efficient.)

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10

class Solution {
public:
    int findInteger(int n, int t) {
        for (int x = n; ; ++x) {
            int prod = 1, y = x;
            while (y) { prod *= y % 10; y /= 10; }
            if (prod % t == 0) return x;
        }
    }
};
1
2
3
4
5
6
7
8
9

class Solution {
    public int findInteger(int n, int t) {
        for (int x = n; ; ++x) {
            int prod = 1, y = x;
            while (y > 0) { prod *= y % 10; y /= 10; }
            if (prod % t == 0) return x;
        }
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12

class Solution:
    def findInteger(self, n: int, t: int) -> int:
        x = n
        while True:
            prod = 1
            y = x
            while y:
                prod *= y % 10
                y //= 10
            if prod % t == 0:
                return x
            x += 1

Complexity

  • ⏰ Time complexity: O(1) in practice (since n and t are small, at most a few hundred iterations).
  • 🧺 Space complexity: O(1) — No extra space used.