LeetCode 2520 - Count the Digits That Divide a Number

LeetCode Problem 2520

Difficulty: 🟢 Easy
Topics: Math

Solution

Problem Understanding

The problem asks us to determine, given a positive integer num, how many of its digits evenly divide num. In other words, for each digit d in the number, we check if num % d == 0. The input is a single integer between 1 and 10^9, and the number will not contain a zero, so we do not need to handle division by zero. The output is a single integer representing the count of digits that are divisors of num.

To restate, if num is 121, we examine its digits 1, 2, and 1. Both occurrences of 1 divide 121, but 2 does not. Therefore, the answer is 2. The constraints indicate that the input size is manageable; the number of digits in num is at most 9, so even a simple iteration over digits is efficient. Important edge cases include numbers with repeated digits, prime numbers, and the largest possible numbers up to 10^9.

Approaches

The brute-force approach involves converting num to a string or extracting digits using modulo operations, then checking each digit to see if it divides num. This works because the number of digits is small, but it iterates over each digit separately and performs a division check each time. Given that there are at most 9 digits, this approach is acceptable, though it is not theoretically optimal if the number of digits were larger.

The optimal approach relies on the same idea but emphasizes careful handling of repeated digits and zero avoidance (though zeros are guaranteed not to appear in this problem). The key insight is that every digit can be individually checked without concern for duplicates or order, and the modulo operation is constant time. Therefore, iterating over the digits and counting valid divisors is both simple and efficient.

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(d)	O(d)	Convert number to string, check each digit for divisibility. d is number of digits.
Optimal	O(d)	O(1)	Iterate through digits using modulo/division, count valid divisors directly.

Algorithm Walkthrough

1. Initialize a counter variable count to zero. This will track the number of digits that divide num.
2. Create a copy of the input number in a temporary variable n to extract digits without modifying the original number.
3. Loop while n > 0. In each iteration:

a. Extract the last digit using digit = n % 10.

b. If digit is not zero and num % digit == 0, increment count by one.

c. Remove the last digit from n using integer division n //= 10. 4. After processing all digits, return count.

Why it works: Each digit is independently checked against num for divisibility. By iterating through all digits, the algorithm guarantees that every possible digit divisor is counted. The guarantee that digits are non-zero avoids division by zero errors.

Python Solution

class Solution:
    def countDigits(self, num: int) -> int:
        count = 0
        n = num
        while n > 0:
            digit = n % 10
            if digit != 0 and num % digit == 0:
                count += 1
            n //= 10
        return count

The Python implementation follows the algorithm step by step. A copy of num is stored in n so that the original value remains unchanged for modulo checks. The while loop iterates through all digits from right to left, performing the divisibility check and updating count. Finally, the accumulated count is returned.

Go Solution

func countDigits(num int) int {
    count := 0
    n := num
    for n > 0 {
        digit := n % 10
        if digit != 0 && num % digit == 0 {
            count++
        }
        n /= 10
    }
    return count
}

In Go, the implementation is similar. We use a for loop to iterate through the digits of num and a variable count to track the number of divisors. Integer division and modulo operations behave the same as in Python. No special handling for zero is needed because the constraints guarantee non-zero digits.

Worked Examples

Example 1: num = 7

Step	n	digit	num % digit	count
Start	7	-	-	0
Iteration 1	7	7	0	1
End	0	-	-	1

Example 2: num = 121

Step	n	digit	num % digit	count
Start	121	-	-	0
Iteration 1	121	1	0	1
Iteration 2	12	2	1	1
Iteration 3	1	1	0	2
End	0	-	-	2

Example 3: num = 1248

Step	n	digit	num % digit	count
Start	1248	-	-	0
Iteration 1	1248	8	0	1
Iteration 2	124	4	0	2
Iteration 3	12	2	0	3
Iteration 4	1	1	0	4
End	0	-	-	4

Complexity Analysis

Measure	Complexity	Explanation
Time	O(d)	Each digit is processed once, where d is the number of digits in num (at most 9).
Space	O(1)	Only a few integer variables are used; no additional data structures required.

Because the number of digits is small (max 9 for 10^9), the time complexity is effectively constant. Space complexity is minimal since no arrays or strings are created.

Test Cases

# Basic examples
assert Solution().countDigits(7) == 1  # single-digit prime
assert Solution().countDigits(121) == 2  # repeated digit 1
assert Solution().countDigits(1248) == 4  # divisible by all digits

# Edge cases
assert Solution().countDigits(1) == 1  # smallest number
assert Solution().countDigits(10**9) == 1  # large number, only last digit divides
assert Solution().countDigits(222) == 3  # all digits are same and divide
assert Solution().countDigits(13579) == 1  # prime digits only

Test	Why
7	single-digit number, divides itself
121	repeated digits, checks counting of duplicates
1248	all digits divide the number
1	minimum input boundary
10^9	maximum input boundary
222	repeated digits, all divisors
13579	digits that are prime, not all divide

Edge Cases

The first edge case is the smallest number, 1. It is important because it tests whether the algorithm handles single-digit inputs correctly and counts the number itself. The second edge case is numbers with repeated digits, like 222 or 121. This tests if the solution correctly counts each occurrence of a divisor, not just unique digits. The third edge case is large numbers near 10^9, which checks that integer handling and performance remain correct, although the constraints guarantee it is feasible. The solution handles all these correctly using simple digit extraction and modulo checks.