# 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:

```python
[left, right]
```

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

For example, `128` is self-dividing because:

```python
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:

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

## Input and Output

| Item | Meaning |
|---|---|
| Input | Two integers `left` and `right` |
| Output | A list of all self-dividing numbers in the range |
| Range | Both `left` and `right` are included |
| Invalid digit | Any number containing `0` is not self-dividing |

Example function shape:

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

## Examples

### Example 1

```python
left = 1
right = 22
```

The self-dividing numbers are:

```python
[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:

```python
12 % 1 == 0
12 % 2 == 0
```

`15` is self-dividing because:

```python
15 % 1 == 0
15 % 5 == 0
```

`22` is self-dividing because:

```python
22 % 2 == 0
22 % 2 == 0
```

### Example 2

```python
left = 47
right = 85
```

The answer is:

```python
[48, 55, 66, 77]
```

`48` works because:

```python
48 % 4 == 0
48 % 8 == 0
```

`55` works because:

```python
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:

```python
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:

```python
x = 128
```

We need to test:

```python
128 % 8
128 % 2
128 % 1
```

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

```python
128 -> 12 -> 1 -> 0
```

So we use two variables:

```python
original = x
current = x
```

`current` is used to extract digits.

`original` is used for divisibility checks.

To get the last digit:

```python
digit = current % 10
```

To remove the last digit:

```python
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:

```python
n = right - left + 1
```

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

| Metric | Value | Why |
|---|---:|---|
| Time | `O(n * d)` | We check each number and scan its digits |
| Space | `O(1)` extra | The helper uses only a few variables |

The returned list is not counted as extra working space.

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

## Implementation

```python
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:

```python
original = x
```

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

The loop processes one digit at a time:

```python
while x > 0:
```

The last digit is:

```python
digit = x % 10
```

If the digit is zero, the number is invalid:

```python
if digit == 0:
    return False
```

Otherwise, we check divisibility using the original number:

```python
if original % digit != 0:
    return False
```

Then we remove the digit:

```python
x //= 10
```

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

```python
return True
```

The outer loop tests every number in the range:

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

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

## Testing

```python
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()
```

| Test | Why |
|---|---|
| `1` to `22` | Official-style basic range |
| `47` to `85` | Larger two-digit range |
| `10` to `10` | Contains zero |
| `11` to `11` | Single valid number |
| `100` to `105` | All contain zero or fail divisibility |