E3345.最小可整除数位乘积 I

https://leetcode.cn/problems/smallest-divisible-digit-product-i/

给你两个整数 n 和 t 。请你返回大于等于 n 的 最小 整数，且该整数的 各数位之积 能被 t 整除。

示例 1：

输入：n = 10, t = 2

输出：10

解释：

10 的数位乘积为 0 ，可以被 2 整除，所以它是大于等于 10 且满足题目要求的最小整数。

示例 2：

输入：n = 15, t = 3

输出：16

解释：

16 的数位乘积为 6 ，可以被 3 整除，所以它是大于等于 15 且满足题目要求的最小整数。

提示：

• 1 <= n <= 100
• 1 <= t <= 10

这道题的要求是找到大于等于 n 的最小整数，使得该整数的各数位之积能够被 t 整除。

由于题目中的输入范围很小（n <= 100，t <= 10），可以直接从 n 开始向上逐个枚举每个整数，计算其数位乘积并判断是否能被 t 整除。由于任何包含数字 0 的整数（例如 10、20、100 等）数位乘积都为 0，而 0 可以被任何正整数 t 整除，因此最多只需要枚举几次就能找到符合条件的答案。

Python 代码实现

class Solution:

    def smallestNumber(self, n: int, t: int) -> int:
        while True:
            # 计算当前数字 n 的各数位之积
            prod = 1
            for digit in str(n):
                prod *= int(digit)

            # 判断乘积是否能被 t 整除
            if prod % t == 0:
                return n

            n += 1

复杂度分析

• 时间复杂度：$\mathcal{O}(1)$。因为最多增加到下一个包含 0 的数字（最多增加 10 次）就会停止循环，且数字最多只有 3 位（$n\le 100$），因此时间开销是常数级别的。
• 空间复杂度：$\mathcal{O}(1)$。只使用了有限的几个局部变量。