LeetCode 728: Self Dividing Numbers

Problem Restatement

We are given two integers, left and right.

We need to return all self-dividing numbers in the inclusive range:

[left, right]

A self-dividing number is divisible by every digit it contains.

For example, 128 is self-dividing because:

128 % 1 == 0
128 % 2 == 0
128 % 8 == 0

A self-dividing number cannot contain the digit 0, because division by zero is not allowed.

The official constraint is:

1 <= left <= right <= 10^4

Input and Output

Example function shape:

def selfDividingNumbers(left: int, right: int) -> list[int]:
    ...

Examples

Example 1

left = 1
right = 22

The self-dividing numbers are:

[1, 2, 3, 4, 5, 6, 7, 8, 9, 11, 12, 15, 22]

Numbers from 1 to 9 are self-dividing because each number has one digit and is divisible by itself.

10 is not self-dividing because it contains 0.

12 is self-dividing because:

12 % 1 == 0
12 % 2 == 0

15 is self-dividing because:

15 % 1 == 0
15 % 5 == 0

22 is self-dividing because:

22 % 2 == 0
22 % 2 == 0

Example 2

left = 47
right = 85

The answer is:

[48, 55, 66, 77]

48 works because:

48 % 4 == 0
48 % 8 == 0

55 works because:

55 % 5 == 0
55 % 5 == 0

First Thought: Check Every Number

The constraints are small. Since right <= 10^4, we can check every number in the range.

For each number, we inspect its digits.

A number is valid if:

1. None of its digits is 0.
2. Every digit divides the original number exactly.

So the main task is writing a helper function:

is_self_dividing(x)

This function returns True if x is self-dividing, and False otherwise.

Key Insight

When checking a number, we must keep the original number unchanged.

For example, suppose:

x = 128

We need to test:

128 % 8
128 % 2
128 % 1

But if we extract digits using division, the working value changes:

128 -> 12 -> 1 -> 0

So we use two variables:

original = x
current = x

current is used to extract digits.

original is used for divisibility checks.

To get the last digit:

digit = current % 10

To remove the last digit:

current //= 10

Algorithm

Create an empty answer list.

For every number x from left to right:

1. Check whether x is self-dividing.
2. If it is, append it to the answer list.

To check whether x is self-dividing:

1. Store original = x.
2. While x > 0:
   • Extract the last digit with x % 10.
   • If the digit is 0, return False.
   • If original % digit != 0, return False.
   • Remove the last digit with x //= 10.
3. Return True.

Correctness

The helper function examines every digit of the candidate number.

At each step, x % 10 gives the current last digit, and x //= 10 removes that digit. Repeating this process eventually visits all digits exactly once.

If any digit is 0, the helper returns False. This is correct because a self-dividing number is not allowed to contain zero.

If any digit does not divide the original number, the helper returns False. This is correct because a self-dividing number must be divisible by every digit it contains.

If the loop finishes, then every digit was nonzero and every digit divided the original number. Therefore the number is self-dividing.

The outer loop checks every integer in the inclusive range [left, right]. It appends exactly the numbers accepted by the helper. Therefore the returned list contains exactly all self-dividing numbers in the required range.

Complexity

Let:

n = right - left + 1

Let d be the maximum number of digits among numbers in the range.

The returned list is not counted as extra working space.

Since right <= 10^4, d is at most 5.

Implementation

class Solution:
    def selfDividingNumbers(self, left: int, right: int) -> list[int]:
        def is_self_dividing(x: int) -> bool:
            original = x

            while x > 0:
                digit = x % 10

                if digit == 0:
                    return False

                if original % digit != 0:
                    return False

                x //= 10

            return True

        answer = []

        for x in range(left, right + 1):
            if is_self_dividing(x):
                answer.append(x)

        return answer

Code Explanation

The helper function starts by saving the unchanged number:

original = x

This matters because x will be reduced while we extract digits.

The loop processes one digit at a time:

while x > 0:

The last digit is:

digit = x % 10

If the digit is zero, the number is invalid:

if digit == 0:
    return False

Otherwise, we check divisibility using the original number:

if original % digit != 0:
    return False

Then we remove the digit:

x //= 10

If all digits pass, the number is self-dividing:

return True

The outer loop tests every number in the range:

for x in range(left, right + 1):

The + 1 is needed because Python ranges exclude the right endpoint.

Testing

def run_tests():
    s = Solution()

    assert s.selfDividingNumbers(1, 22) == [
        1, 2, 3, 4, 5, 6, 7, 8, 9, 11, 12, 15, 22
    ]

    assert s.selfDividingNumbers(47, 85) == [48, 55, 66, 77]
    assert s.selfDividingNumbers(10, 10) == []
    assert s.selfDividingNumbers(11, 11) == [11]
    assert s.selfDividingNumbers(100, 105) == []

    print("all tests passed")

run_tests()