#2520

Easy

auto_awesomeMath-driven solution strategy

LeetCode Problem Workspace

Count the Digits That Divide a Number

Count the digits that divide a number by checking each digit's divisibility.

Problem Statement

Given a positive integer num, return the number of digits in num that divide num evenly. An integer divides another number if the result of the modulo operation between them is zero. For example, for num = 121, the digits are 1, 2, and 1. The digit 1 divides 121, but the digit 2 does not, as 121 % 2 != 0. Therefore, the correct answer is 2.

You are guaranteed that the number will not contain the digit 0, so you don't need to handle division by zero. The approach involves iterating through each digit of num, checking its divisibility, and counting the successful divisions. This ensures that the final result reflects how many digits divide the number without leaving a remainder.

Examples

Example 1

Input: num = 7

Output: 1

7 divides itself, hence the answer is 1.

Example 2

Input: num = 121

Output: 2

121 is divisible by 1, but not 2. Since 1 occurs twice as a digit, we return 2.

Example 3

Input: num = 1248

Output: 4

1248 is divisible by all of its digits, hence the answer is 4.

Constraints

1 <= num <= 109
num does not contain 0 as one of its digits.

Solution Approach

Extract and check each digit

The most straightforward approach is to iterate through each digit of num, extract it using modulo and integer division, and check if it divides num. You can do this by checking if num % digit == 0.

Iterate through the digits

You can extract digits from the number by using num % 10 to get the least significant digit and then reducing num by dividing it by 10. Continue this process until all digits are checked.

Edge case handling

The problem guarantees no zeroes in the number, so there is no need to check for division by zero. Just focus on checking each digit’s divisibility.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

Time 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.

What Interviewers Usually Probe

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

Common Pitfalls or Variants

Common pitfalls

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

Follow-up variants

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

FAQ

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.

terminal

Solution

Solution 1: Enumeration

We directly enumerate each digit $val$ of the integer $num$, and if $val$ can divide $num$, we add one to the answer.

1

2

3

4

5

6

7

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

Solution 2

#### TypeScript

1

2

3

4

5

6

7

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

Continue Practicing

#2521 distinct prime factors of product of array #2523 closest prime numbers in range #2525 categorize box according to criteria