# Smallest Divisible Digit Product I
**Difficulty:** EASY
[External](https://leetcode.com/problems/smallest-divisible-digit-product-i)
Canonical: https://scaleengineer.com/dsa/problems/smallest-divisible-digit-product-i
**Patterns:** [Math](https://scaleengineer.com/dsa/patterns/math), [Enumeration](https://scaleengineer.com/dsa/patterns/enumeration)
---
## 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 <= 100`
* `1 <= t <= 10`

# Approaches
## Pre-computation with Linear Scan
This method involves pre-calculating the digit products for a range of numbers and storing them. When a query comes, it scans through the pre-computed values starting from `n` to find the first number that satisfies the divisibility condition. This approach trades space for time, aiming to speed up repeated queries by avoiding re-computation.
**Time:** Pre-computation: `O(L * log L)` where `L` is the limit. Query: `O(L - n)`. For a single execution, the total time is dominated by pre-computation, making it less efficient than a direct approach for the given problem scale. · **Space:** `O(L)` to store the pre-computed digit products, where `L` is the chosen limit. Since `L` is a constant, this can be considered `O(1)`.
**Pros:** Efficient for multiple test cases or queries, as the expensive calculations are done only once.; The lookup time for each query is fast, involving just an array access and a check.
**Cons:** Requires extra space to store the pre-computed values (`O(LIMIT)`).; The pre-computation step is an upfront cost which might be slower than a direct approach if only one query is made.; It relies on a hardcoded limit, which might fail if the constraints were larger.
### Explanation
Given the small constraints (`n <= 100`), the answer is expected to be a relatively small number. We can establish a fixed upper limit, for instance, 200, which should comfortably contain the answer for any valid input.\nAn array, let's call it `digitProducts`, is used to store the product of digits for each number from 1 up to this limit.\nThis array is populated once, possibly in a static initializer block. For each number `i` in the range, its digit product is calculated and stored at `digitProducts[i]`.\nThe `smallestDivisibleDigitProduct` function then iterates from `n` up to the limit. For each number `i`, it retrieves the pre-computed product `digitProducts[i]` and checks if it's divisible by `t`.\nThe first number `i` that satisfies `digitProducts[i] % t == 0` is the smallest such number greater than or equal to `n`, so it is returned.\nA fallback mechanism for numbers beyond the limit can be included for robustness, although it's unlikely to be triggered with the given constraints.\n```java\nclass Solution {\n    private static final int LIMIT = 200;\n    private static final long[] digitProducts = new long[LIMIT + 1];\n\n    static {\n        digitProducts[0] = 0;\n        for (int i = 1; i <= LIMIT; i++) {\n            digitProducts[i] = calculateDigitProduct(i);\n        }\n    }\n\n    private static long calculateDigitProduct(int n) {\n        if (n == 0) return 0;\n        long product = 1;\n        int temp = n;\n        while (temp > 0) {\n            int digit = temp % 10;\n            if (digit == 0) return 0; // Optimization\n            product *= digit;\n            temp /= 10;\n        }\n        return product;\n    }\n\n    public long smallestDivisibleDigitProduct(int n, int t) {\n        for (int i = n; i <= LIMIT; i++) {\n            if (digitProducts[i] % t == 0) {\n                return i;\n            }\n        }\n        // Fallback for cases where answer > LIMIT\n        long num = LIMIT + 1;\n        while (true) {\n            if (calculateDigitProduct((int)num) % t == 0) {\n                return num;\n            }\n            num++;\n        }\n    }\n}\n```
### Algorithm
1. Define a constant `LIMIT` (e.g., 200) as the upper bound for pre-computation.\n2. Create a static array `digitProducts` of size `LIMIT + 1`.\n3. In a static block, iterate from `i = 1` to `LIMIT`.\n4. For each `i`, calculate its digit product and store it in `digitProducts[i]`.\n5. In the main function, iterate with `i` from `n` to `LIMIT`.\n6. Check if `digitProducts[i]` is divisible by `t`.\n7. If it is, return `i` as the result.\n8. If the loop finishes without finding an answer (unlikely), implement a fallback to check numbers greater than `LIMIT`.

## Simple Iteration (Brute-Force)
This is a straightforward and highly effective approach for the given constraints. It iterates upwards from `n`, and for each number, it calculates the product of its digits on-the-fly. The first number whose digit product is divisible by `t` is the answer.
**Time:** `O((K - n) * log K)`, where `K` is the final answer. Since `K` is very close to `n` for the given constraints, the complexity is very low in practice. · **Space:** `O(1)` extra space is used.
**Pros:** Extremely simple to understand and implement.; Requires minimal space (`O(1)`).; Very fast for the given constraints, as the number of iterations is very small.
**Cons:** Theoretically, if `n` and `t` were very large, the loop could run for a long time, making it inefficient. However, this is not a concern for this problem.
### Explanation
The core idea is to perform a linear search for the answer. We start with the number `n` and check if it satisfies the condition. If not, we check `n+1`, then `n+2`, and so on, until we find a valid number.\nThe algorithm is implemented with a `while` loop that starts with `num = n`.\nInside the loop, a helper function `getDigitProduct(num)` is called. This function computes the product of the digits of `num`.\nThe `getDigitProduct` function is implemented by repeatedly taking the number modulo 10 to get the last digit and then dividing by 10. An important optimization is to recognize that if any digit is 0, the product is 0.\nThe calculated product is then checked for divisibility by `t` using the modulo operator (`product % t == 0`).\nIf the condition is met, the loop terminates, and the current `num` is returned. Otherwise, `num` is incremented, and the process repeats.\nGiven the small constraints on `n` and `t`, the answer is always found after a very small number of iterations, making this approach extremely fast in practice.\n```java\nclass Solution {\n    private long getDigitProduct(long n) {\n        if (n == 0) {\n            return 0;\n        }\n        long product = 1;\n        long temp = n;\n        while (temp > 0) {\n            long digit = temp % 10;\n            if (digit == 0) {\n                // If any digit is 0, the product is 0.\n                return 0;\n            }\n            product *= digit;\n            temp /= 10;\n        }\n        return product;\n    }\n\n    public long smallestDivisibleDigitProduct(int n, int t) {\n        long num = n;\n        while (true) {\n            if (getDigitProduct(num) % t == 0) {\n                return num;\n            }\n            num++;\n        }\n    }\n}\n```
### Algorithm
1. Initialize a variable `num` with the input `n`.\n2. Enter an infinite `while` loop.\n3. Inside the loop, calculate the product of the digits of `num`.\n   a. Handle the case where `num` has a digit 0; the product is 0.\n   b. Otherwise, iterate through the digits of `num` by repeatedly using modulo 10 and division by 10, multiplying them into a running product.\n4. Check if the calculated digit product is divisible by `t`.\n5. If `product % t == 0`, then `num` is the answer. Return `num`.\n6. If not, increment `num` by 1 and continue the loop.

# Solutions
### Java

```java
class Solution {
public
  int smallestNumber(int n, int t) {
    for (int i = n;; ++i) {
      int p = 1;
      for (int x = i; x > 0; x /= 10) {
        p *= (x % 10);
      }
      if (p % t == 0) {
        return i;
      }
    }
  }
}

```

### CPP

```cpp
class Solution {
public:
  int smallestNumber(int n, int t) {
    for (int i = n;; ++i) {
      int p = 1;
      for (int x = i; x > 0; x /= 10) {
        p *= (x % 10);
      }
      if (p % t == 0) {
        return i;
      }
    }
  }
};

```

### Python

```python
class Solution:
    def smallestNumber(self, n: int, t: int) -> int: for i in count(n): p = 1 x = i while x: p *= x % 10 x //= 10 if p % t == 0: return i

```