Problem Description

A self-dividing number is a special type of number that can be evenly divided by each of its own digits.

For example, consider the number 128:

• 128 % 1 = 0 (divisible by 1)
• 128 % 2 = 0 (divisible by 2)
• 128 % 8 = 0 (divisible by 8)

Since 128 is divisible by all of its digits (1, 2, and 8), it is a self-dividing number.

There's one important restriction: a self-dividing number cannot contain the digit 0. This makes sense because division by zero is undefined.

Given two integers left and right that define a range, you need to find all self-dividing numbers within this range (including both left and right themselves) and return them as a list.

For instance, if left = 1 and right = 22, you would check each number from 1 to 22 to see if it's self-dividing. Numbers like 1, 2, 3, 4, 5, 6, 7, 8, 9, 11, 12, 15, and 22 would all be self-dividing numbers in this range.

Intuition

The problem asks us to identify numbers with a specific property - being divisible by each of their own digits. The most straightforward way to check this property is to extract each digit from the number and test divisibility.

To extract digits from a number, we can use the modulo operator (%). For any number, n % 10 gives us the last digit. After getting the last digit, we can remove it by integer division (n // 10). By repeating this process, we can extract all digits one by one.

For example, with 128:

• 128 % 10 = 8 (last digit)
• 128 // 10 = 12 (remove last digit)
• 12 % 10 = 2 (next digit)
• 12 // 10 = 1 (remove that digit)
• 1 % 10 = 1 (final digit)
• 1 // 10 = 0 (done)

For each extracted digit, we need to check two things:

1. Is the digit 0? If yes, the number cannot be self-dividing (division by zero is undefined)
2. Does the original number divide evenly by this digit? If not, it's not self-dividing

The key insight is that we need to preserve the original number while extracting its digits. That's why in the solution, we use a separate variable y to manipulate and extract digits, while keeping x intact for the divisibility checks.

Since we need to check every number in the given range [left, right], we simply iterate through this range and apply our checking function to each number, collecting those that pass the test.

Learn more about Math patterns.

Solution Approach

The solution implements a simulation approach by checking each number in the given range to determine if it's self-dividing.

We define a helper function check(x) that determines whether a number x is self-dividing. The implementation works as follows:

1. Create a working copy: We use variable y to store a copy of x. This allows us to extract digits from y while preserving the original value x for divisibility checks.

2. Extract and check each digit: We enter a loop that continues while y > 0:

   • Extract the last digit using y % 10
   • Check if this digit is 0 - if it is, immediately return False since division by zero is invalid
   • Check if x % (y % 10) != 0 - if the original number is not divisible by this digit, return False
   • Remove the last digit from y using integer division: y //= 10

3. Return result: If we successfully check all digits without returning False, the number is self-dividing, so we return True.

The main function uses a list comprehension to generate the result:

return [x for x in range(left, right + 1) if check(x)]

This iterates through all numbers from left to right (inclusive), applies the check function to each number, and includes only those that return True in the final list.

The time complexity is O((right - left) * log(max_num)) where max_num is the largest number in the range, since for each number we need to extract all its digits (which takes O(log(num)) time). The space complexity is O(1) for the checking function itself, though the output list requires O(k) space where k is the count of self-dividing numbers in the range.

Example Walkthrough

Let's walk through finding self-dividing numbers in the range [47, 50].

Checking 47:

• Start with x = 47, create copy y = 47
• Extract first digit: y % 10 = 7
  • Is it 0? No, continue
  • Is 47 % 7 = 0? No, 47 % 7 = 5
  • Since 47 is not divisible by 7, return False
• Result: 47 is not self-dividing

Checking 48:

• Start with x = 48, create copy y = 48
• Extract first digit: y % 10 = 8
  • Is it 0? No, continue
  • Is 48 % 8 = 0? Yes, continue
  • Update: y = y // 10 = 4
• Extract second digit: y % 10 = 4
  • Is it 0? No, continue
  • Is 48 % 4 = 0? Yes, continue
  • Update: y = y // 10 = 0
• Loop ends (y = 0), return True
• Result: 48 is self-dividing

Checking 49:

• Start with x = 49, create copy y = 49
• Extract first digit: y % 10 = 9
  • Is it 0? No, continue
  • Is 49 % 9 = 0? No, 49 % 9 = 4
  • Since 49 is not divisible by 9, return False
• Result: 49 is not self-dividing

Checking 50:

• Start with x = 50, create copy y = 50
• Extract first digit: y % 10 = 0
  • Is it 0? Yes, immediately return False
• Result: 50 is not self-dividing (contains 0)

Final Answer: [48] - only 48 is self-dividing in the range [47, 50]

Solution Implementation

Time and Space Complexity

Time Complexity: O(n × log₁₀ M), where n is the number of integers in the interval [left, right] (i.e., n = right - left + 1), and M = right is the maximum value in the interval.

• The outer loop iterates through all integers from left to right, which gives us n iterations.
• For each integer x, the check function examines each digit of the number.
• The number of digits in an integer x is ⌊log₁₀ x⌋ + 1, which is O(log₁₀ x).
• In the worst case, we check the largest number in the range, which is right = M, giving us O(log₁₀ M) operations per number.
• Therefore, the total time complexity is O(n × log₁₀ M).

Space Complexity: O(1) for the algorithm itself (excluding the output list).

• The check function uses only a constant amount of extra space with variables y and temporary calculations.
• The list comprehension creates an output list that can contain up to n elements in the worst case (when all numbers are self-dividing), which would be O(n) space for the output.
• If we consider only the auxiliary space used by the algorithm (not counting the space needed for the output), the space complexity is O(1).

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

Common Pitfalls

1. Forgetting to Handle the Zero Digit

One of the most common mistakes is forgetting to check for the digit 0 before attempting division. This can lead to a runtime error due to division by zero.

Incorrect approach:

def is_self_dividing(num: int) -> bool:
    temp = num
    while temp > 0:
        digit = temp % 10
        if num % digit != 0:  # Runtime error when digit is 0!
            return False
        temp //= 10
    return True

Solution: Always check if the digit is 0 before performing the modulo operation:

if digit == 0 or num % digit != 0:
    return False

2. Modifying the Original Number During Digit Extraction

Another pitfall is directly modifying the original number while extracting digits, which makes it impossible to check divisibility later.

Incorrect approach:

def is_self_dividing(num: int) -> bool:
    while num > 0:
        digit = num % 10
        if digit == 0 or num % digit != 0:  # num is being modified!
            return False
        num //= 10  # This changes num, affecting divisibility checks
    return True

Solution: Create a copy of the number for digit extraction while preserving the original for divisibility checks:

temp = num  # Create a copy
while temp > 0:
    digit = temp % 10
    if digit == 0 or num % digit != 0:  # Use original num for division
        return False
    temp //= 10  # Modify only the copy

3. Using String Conversion Inefficiently

While converting to string works, it's less efficient and can introduce unnecessary overhead:

Less optimal approach:

def is_self_dividing(num: int) -> bool:
    str_num = str(num)
    if '0' in str_num:
        return False
    for digit_char in str_num:
        if num % int(digit_char) != 0:
            return False
    return True

Solution: The mathematical approach using modulo and integer division is more efficient and avoids string conversion overhead, especially for large ranges.

4. Off-by-One Error in Range

Forgetting that the range should be inclusive of both endpoints.

Incorrect approach:

return [num for num in range(left, right) if is_self_dividing(num)]  # Excludes 'right'

Solution: Use range(left, right + 1) to include the right boundary:

return [num for num in range(left, right + 1) if is_self_dividing(num)]