Problem Description

You are given a positive integer num. Your task is to count how many digits in num can divide num evenly (with no remainder).

A digit val divides num if num % val == 0.

For example:

• If num = 7, the only digit is 7, and since 7 divides 7 evenly, the answer is 1.
• If num = 121, the digits are 1, 2, and 1. The number 121 is divisible by 1 (appears twice) but not by 2. Since digit 1 appears twice and both occurrences divide 121, the answer is 2.
• If num = 1248, the digits are 1, 2, 4, and 8. All four digits divide 1248 evenly, so the answer is 4.

The solution iterates through each digit of the number by repeatedly dividing by 10 and extracting the remainder. For each digit val, it checks if num % val == 0. The variable ans keeps track of how many digits satisfy this condition. The divmod(x, 10) function efficiently computes both the quotient and remainder in one operation, where the remainder gives us the current digit and the quotient becomes the new number for the next iteration.

Key points:

• The input number will not contain the digit 0
• Each digit occurrence is counted separately (if a digit appears multiple times, each occurrence is checked)
• The number ranges from 1 to 10^9

Intuition

To solve this problem, we need to check each digit of the number individually to see if it divides the original number evenly. The most straightforward way to access each digit is to extract them one by one.

How do we extract digits from a number? Think about how we normally break down a number into its digits - we can use the modulo operation. When we do num % 10, we get the last digit. To move to the next digit, we divide the number by 10 (using integer division). This process naturally gives us digits from right to left.

For example, with num = 1248:

• 1248 % 10 = 8 (last digit)
• 1248 // 10 = 124 (remaining number)
• 124 % 10 = 4 (next digit)
• 124 // 10 = 12 (remaining number)
• And so on...

Once we have each digit, we simply check if the original number is divisible by that digit using the modulo operation: num % digit == 0. If true, we increment our counter.

The clever part of the solution is using divmod(x, 10) which gives us both the quotient and remainder in one operation - the quotient becomes our new number for the next iteration, and the remainder is the current digit we need to check. This makes the code more efficient and concise.

We continue this process until we've extracted all digits (when x becomes 0), and return the total count of digits that divide the original number.

Learn more about Math patterns.

Solution Approach

The solution uses a simple enumeration approach where we extract and check each digit of the number one by one.

Here's the step-by-step implementation:

1. Initialize variables: We start with ans = 0 to count the number of digits that divide num, and x = num as a working copy of the number that we'll modify during iteration.

2. Extract digits using a while loop: We continue the loop while x > 0. In each iteration:

   • Use divmod(x, 10) to get both the quotient and remainder
   • The quotient becomes the new value of x for the next iteration
   • The remainder val is the current digit we extracted

3. Check divisibility: For each extracted digit val, we check if num % val == 0. If true, the digit divides the original number evenly.

4. Count valid digits: We use the expression ans += num % val == 0 which adds 1 to ans when the condition is true (Python treats True as 1 and False as 0).

5. Return the result: After processing all digits, return ans.

Let's trace through an example with num = 121:

• First iteration: x = 121, val = 1, check 121 % 1 == 0 (True), ans = 1
• Second iteration: x = 12, val = 2, check 121 % 2 == 0 (False), ans = 1
• Third iteration: x = 1, val = 1, check 121 % 1 == 0 (True), ans = 2
• Loop ends when x = 0, return ans = 2

The time complexity is O(log n) where n is the value of the number, as we process each digit once. The space complexity is O(1) as we only use a constant amount of extra space.

Example Walkthrough

Let's walk through the solution with num = 1248:

Initial Setup:

• ans = 0 (count of digits that divide num)
• x = 1248 (working copy of the number)

Iteration 1:

• divmod(1248, 10) returns (124, 8)
• x = 124 (quotient - remaining number)
• val = 8 (remainder - current digit)
• Check: 1248 % 8 == 0? Yes! (1248 ÷ 8 = 156)
• ans = 0 + 1 = 1

Iteration 2:

• divmod(124, 10) returns (12, 4)
• x = 12
• val = 4
• Check: 1248 % 4 == 0? Yes! (1248 ÷ 4 = 312)
• ans = 1 + 1 = 2

Iteration 3:

• divmod(12, 10) returns (1, 2)
• x = 1
• val = 2
• Check: 1248 % 2 == 0? Yes! (1248 ÷ 2 = 624)
• ans = 2 + 1 = 3

Iteration 4:

• divmod(1, 10) returns (0, 1)
• x = 0
• val = 1
• Check: 1248 % 1 == 0? Yes! (any number is divisible by 1)
• ans = 3 + 1 = 4

Loop ends (x = 0), return ans = 4

All four digits (1, 2, 4, 8) divide 1248 evenly, so the answer is 4.

Solution Implementation

Time and Space Complexity

Time Complexity: O(log num)

The algorithm iterates through each digit of the number num. In each iteration, it performs a division by 10 using divmod(x, 10), which extracts the last digit and reduces x by removing that digit. The number of digits in a number num is floor(log₁₀(num)) + 1, which is O(log num). Each operation within the loop (division, modulo, addition) takes constant time O(1). Therefore, the overall time complexity is O(log num).

Space Complexity: O(1)

The algorithm uses only a fixed amount of extra space regardless of the input size. It maintains three variables: ans for counting valid digits, x as a copy of the input number, and val for storing the current digit. These variables use constant space that doesn't scale with the input. No additional data structures like arrays or recursive call stacks are used. Therefore, the space complexity is O(1).

Learn more about how to find time and space complexity quickly.

Common Pitfalls

1. Division by Zero with Digit 0

The Pitfall: If the number contains the digit 0 (like 102, 305, etc.), attempting to check num % digit when digit = 0 will cause a ZeroDivisionError. This is a runtime error that will crash the program.

Why it happens: When extracting digits using divmod(temp_num, 10), any 0 digit in the number will be extracted just like any other digit. The modulo operation with 0 as the divisor is undefined mathematically and raises an exception in Python.

Solution: Add a check to skip any digit that equals 0 before performing the modulo operation:

class Solution:
    def countDigits(self, num: int) -> int:
        count = 0
        temp_num = num
      
        while temp_num > 0:
            temp_num, digit = divmod(temp_num, 10)
          
            # Skip if digit is 0 to avoid division by zero
            if digit != 0 and num % digit == 0:
                count += 1
      
        return count

2. Using the Same Variable for Iteration and Division Check

The Pitfall: If you accidentally use the modified temp_num instead of the original num for the divisibility check:

# WRONG: Using temp_num instead of num for divisibility check
count += (temp_num % digit == 0)  # This checks the wrong number!

Why it happens: After extracting a digit, temp_num has been modified and no longer represents the original number. Checking divisibility against temp_num will give incorrect results.

Solution: Always use the original num value for the divisibility check, keeping temp_num solely for digit extraction:

# CORRECT: Use original num for divisibility check
count += (num % digit == 0)

3. Integer Division Confusion in Other Languages

The Pitfall: When translating this solution to languages like C++ or Java, using integer division / instead of proper remainder extraction can lead to incorrect digit extraction.

Why it happens: In some languages, you might write digit = temp_num / 10 thinking it gives the last digit, but this actually gives the quotient, not the remainder.

Solution: Ensure you're using the modulo operator for digit extraction:

• Python: temp_num, digit = divmod(temp_num, 10) or digit = temp_num % 10
• C++/Java: digit = temp_num % 10; temp_num = temp_num / 10;

These pitfalls highlight the importance of careful handling of edge cases and understanding the difference between the working variables and the original input when implementing digit manipulation algorithms.