What is the time complexity of this problem?

The time complexity is constant, as you only check at most 10 numbers.

How can I optimize the solution for larger values of n?

For this problem, optimization is unnecessary due to the small range of n, but for larger ranges, consider avoiding redundant checks or skipping numbers with non-divisible digit products.

What happens if a number contains a zero in its digits?

If a number contains zero as a digit, its digit product will automatically be zero, which is divisible by any t.

How do I handle the case where the digit product is not divisible by t?

In that case, continue searching for the next number until you find one where the product is divisible by t.

Can I use this approach for other types of digit product problems?

Yes, this enumeration approach can be used for various digit product problems, but consider optimizing the product calculation if the range is large.

#3345

Easy

auto_awesome数学·结合·enumeration

LeetCode 题解工作台

最小可整除数位乘积 I

给你两个整数 n 和 t 。请你返回大于等于 n 的最小整数，且该整数的各数位之积能被 t 整除。示例 1：输入： n = 10, t = 2 输出： 10 解释： 10 的数位乘积为 0 ，可以被 2 整除，所以它是大于等于 10 且满足题目要求的最小整数。示例 2：输入： n =…

数学枚举

题目描述

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

lightbulb

解题思路

方法一：枚举

我们注意到，每 $10$ 个数里一定会出现数位乘积为 $0$ 的整数，因此我们可以直接枚举大于等于 $n$ 的整数，直到找到一个数位乘积能被 $t$ 整除的整数。

时间复杂度 $O(\log n)$ ，空间复杂度 $O(1)$ 。

1

2

3

4

5

6

7

8

9

10

11

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

speed

复杂度分析

指标	值
时间	Depends on the final approach
空间	Depends on the final approach

psychology

面试官常问的追问

外企场景

question_mark
Can the candidate explain their reasoning behind choosing a brute force solution?
question_mark
Does the candidate optimize the search process when possible?
question_mark
Is the candidate able to identify edge cases like numbers with zero as a digit?

warning

常见陷阱

外企场景

error
Failing to correctly compute the product of the digits, especially when digits contain zero.
error
Overcomplicating the solution instead of using a straightforward brute force approach.
error
Not checking enough numbers or missing edge cases where digit products are automatically divisible (e.g., numbers containing zero).

swap_horiz

进阶变体

外企场景

arrow_right_alt
What if t is larger than any possible digit product?
arrow_right_alt
How would the solution change if the range of n was significantly larger?
arrow_right_alt
Can you optimize the digit product calculation to avoid redundant work?

help

常见问题

外企场景

继续练习

#3380 用点构造面积最大的矩形 I #3404 统计特殊子序列的数目 #3411 最长乘积等价子数组