How can I solve the 'Count the Digits That Divide a Number' problem efficiently?

You can efficiently solve the problem by iterating through each digit of the number and checking if it divides the number using modulo arithmetic.

What is the time complexity of solving 'Count the Digits That Divide a Number'?

The time complexity is O(d), where d is the number of digits in the number, as we iterate through each digit once.

Does the number need to contain zero digits?

No, the problem guarantees that the number will not contain any zero digits, so division by zero is not a concern.

How does modulo arithmetic help in this problem?

Modulo arithmetic allows you to check if a digit divides the number evenly by verifying if num % digit == 0.

What is the primary approach for solving 'Count the Digits That Divide a Number'?

The primary approach is a math-driven solution that extracts each digit of the number, checks its divisibility, and counts how many digits divide the number evenly.

#2520

Easy

auto_awesome数学·driven

LeetCode 题解工作台

统计能整除数字的位数

给你一个整数 num ，返回 num 中能整除 num 的数位的数目。如果满足 nums % val == 0 ，则认为整数 val 可以整除 nums 。示例 1：输入： num = 7 输出： 1 解释： 7 被自己整除，因此答案是 1 。示例 2：输入： num = 121 输出： …

数学

题目描述

给你一个整数 num ，返回 num 中能整除 num 的数位的数目。

如果满足 nums % val == 0 ，则认为整数 val 可以整除 nums 。

示例 1：

输入：num = 7
输出：1
解释：7 被自己整除，因此答案是 1 。

示例 2：

输入：num = 121
输出：2
解释：121 可以被 1 整除，但无法被 2 整除。由于 1 出现两次，所以返回 2 。

示例 3：

输入：num = 1248
输出：4
解释：1248 可以被它每一位上的数字整除，因此答案是 4 。

提示：

1 <= num <= 10⁹
num 的数位中不含 0

lightbulb

解题思路

方法一：枚举

我们直接枚举整数 $num$ 的每一位上的数 $val$ ，若 $val$ 能够整除 $num$ ，那么答案加一。

枚举结束后，返回答案即可。

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

1

2

3

4

5

6

7

8

class Solution:
    def countDigits(self, num: int) -> int:
        ans, x = 0, num
        while x:
            x, val = divmod(x, 10)
            ans += num % val == 0
        return ans

speed

复杂度分析

指标	值
时间	complexity is O(d), where d is the number of digits in num. This is because we iterate through each digit once. Space complexity is O(1), as we only need a constant amount of space for storing variables during the iteration.
空间	Depends on the final approach

psychology

面试官常问的追问

外企场景

question_mark
Candidate should demonstrate a clear understanding of modulo arithmetic and its use in digit extraction.
question_mark
They should handle edge cases correctly (though the prompt guarantees no zeroes).
question_mark
The approach should be optimized with respect to time complexity, ensuring that the solution can handle large numbers up to 10^9.

warning

常见陷阱

外企场景

error
Not handling the division check properly and missing digits that divide the number.
error
Attempting to divide by zero (though the problem guarantees no zeros in the number).
error
Failing to correctly extract digits using modulo and integer division.

swap_horiz

进阶变体

外企场景

arrow_right_alt
Change the number's range to a higher value and see if the solution still holds.
arrow_right_alt
Consider solving with a different data structure to track divisibility for large inputs.
arrow_right_alt
Alter the constraints to include cases where zero might be included and test for handling those cases.

help

常见问题

外企场景

继续练习

#2521 数组乘积中的不同质因数数目 #2523 范围内最接近的两个质数 #2525 根据规则将箱子分类