Skip to content

3345. Smallest Divisible Digit Product I

Description

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

Solutions

Solution 1: Enumeration

Thinking

We want the smallest integer at least \(n\) whose digit product is divisible by \(t\). With \(n \le 100\) and \(t \le 10\), a number containing \(0\) appears within ten candidates, and its product \(0\) is always divisible by \(t\).

So a linear scan from \(n\) is bounded by a constant; we need not construct a special number.

For each candidate we multiply digits and return the first \(p\) with \(p \bmod t = 0\).

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)\).

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
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

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
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;
            }
        }
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
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;
            }
        }
    }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
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
        }
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
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;
        }
    }
}

Comments