Easy

题目描述

给你两个整数 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

提示：

  • 你最多需要检查 10 个数字。
  • 使用暴力方法检查每个可能的数字。

解题思路

这道题的思路很直观，由于约束条件很小（n ≤ 100），我们可以使用暴力枚举的方法。

解题思路：

  1. 从 n 开始逐个检查每个数字
  2. 对于每个数字，计算其各位数字的乘积
  3. 检查该乘积是否能被 t 整除
  4. 如果能整除，返回该数字；否则继续检查下一个数字

实现细节：

  • 计算数字乘积时，将数字转换为字符串或通过取余操作逐位提取
  • 注意数字 0 的特殊情况：任何包含 0 的数字，其数字乘积都为 0
  • 0 能被任何非零数整除，这在题目约束下是成立的

由于题目提示最多检查 10 个数字，说明答案不会距离 n 太远，这也验证了暴力方法的可行性。

时间复杂度主要取决于需要检查的数字个数和计算每个数字乘积的时间。

代码实现

class Solution {
public:
    int smallestNumber(int n, int t) {
        for (int num = n; ; num++) {
            int product = 1;
            int temp = num;
            while (temp > 0) {
                product *= temp % 10;
                temp /= 10;
            }
            if (product % t == 0) {
                return num;
            }
        }
        return -1; // 这行不会执行到
    }
};

class Solution:
    def smallestNumber(self, n: int, t: int) -> int:
        num = n
        while True:
            product = 1
            temp = num
            while temp > 0:
                product *= temp % 10
                temp //= 10
            if product % t == 0:
                return num
            num += 1

public class Solution {
    public int SmallestNumber(int n, int t) {
        for (int num = n; ; num++) {
            int product = 1;
            int temp = num;
            while (temp > 0) {
                product *= temp % 10;
                temp /= 10;
            }
            if (product % t == 0) {
                return num;
            }
        }
    }
}

/**
 * @param {number} n
 * @param {number} t
 * @return {number}
 */
var smallestNumber = function(n, t) {
    const getDigitProduct = (num) => {
        let product = 1;
        while (num > 0) {
            product *= num % 10;
            num = Math.floor(num / 10);
        }
        return product;
    };
    
    for (let i = n; ; i++) {
        if (getDigitProduct(i) % t === 0) {
            return i;
        }
    }
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型分析
时间复杂度O(k × log n)，其中 k 是需要检查的数字个数（最多10个），log n 是计算每个数字乘积的时间
空间复杂度O(1)，只使用了常数级别的额外空间

相关题目