LeetCode 728 - Self Dividing Numbers
The problem asks us to find all numbers within a given inclusive range [left, right] that satisfy the definition of a self-dividing number. A self-dividing number has two important properties: 1. Every digit inside the number must divide the number evenly. 2.
Difficulty: 🟢 Easy
Topics: Math
Solution
Problem Understanding
The problem asks us to find all numbers within a given inclusive range [left, right] that satisfy the definition of a self-dividing number.
A self-dividing number has two important properties:
- Every digit inside the number must divide the number evenly.
- The number cannot contain the digit
0.
For example, consider the number 128.
128 % 1 == 0128 % 2 == 0128 % 8 == 0
Since all digits divide the number evenly and none of the digits are zero, 128 is a valid self-dividing number.
Now consider 120.
- The digit
0appears in the number. - Division by zero is invalid.
Therefore, 120 is not a self-dividing number.
The input consists of two integers:
left, the beginning of the rangeright, the end of the range
The output should be a list containing every self-dividing number between left and right, inclusive.
The constraints are relatively small:
1 <= left <= right <= 10^4
This tells us several important things:
- The largest number has at most 5 digits.
- The total number of integers we need to inspect is at most
10^4. - A straightforward digit-by-digit simulation is efficient enough.
The key edge cases involve digits equal to zero and digits that do not divide the number evenly. Another subtle case is single-digit numbers. Every non-zero single-digit number is automatically self-dividing because any number divides itself evenly.
Approaches
Brute Force Approach
The most direct solution is to iterate through every integer from left to right and determine whether it is self-dividing.
For each number:
- Extract every digit one at a time.
- If any digit is zero, reject the number immediately.
- Otherwise, check whether the original number is divisible by that digit.
- If all digits pass the divisibility test, add the number to the result list.
This approach is correct because it directly implements the mathematical definition of a self-dividing number.
Although this is technically brute force, the constraints are small enough that it performs very well in practice. Each number contains at most 5 digits, so the amount of work per number is tiny.
Key Insight for the Optimal Approach
The important observation is that we never need expensive operations or advanced data structures.
Each number can be validated independently using simple digit extraction with modulo and integer division:
digit = n % 10n //= 10
This allows us to process digits efficiently without converting numbers into strings.
The optimal solution is therefore still a range scan, but with efficient digit processing and early termination when a bad digit is found.
Approach Comparison
| Approach | Time Complexity | Space Complexity | Notes |
|---|---|---|---|
| Brute Force | O(n * d) | O(1) | Checks every digit of every number directly |
| Optimal | O(n * d) | O(1) | Uses efficient digit extraction and early rejection |
Here:
n = right - left + 1d = number of digits, at most 5
Since d is bounded by a very small constant, the solution is effectively linear in the size of the range.
Algorithm Walkthrough
- Initialize an empty result list to store all self-dividing numbers.
- Iterate through every integer from
lefttoright, inclusive. Each number will be checked independently. - For the current number, store a copy of the original value because we will modify another variable while extracting digits.
- Repeatedly extract the last digit using modulo operation:
digit = current % 10
This gives the rightmost digit of the number. 5. Check whether the digit is zero. A self-dividing number cannot contain zero because division by zero is undefined. If the digit is zero, immediately reject the number. 6. Check whether the original number is divisible by the digit:
original % digit == 0
If this condition fails for even one digit, the number is not self-dividing. 7. Remove the last digit using integer division:
current //= 10
This moves the algorithm to the next digit. 8. Continue until all digits have been processed. 9. If every digit passes the checks, append the number to the result list. 10. After all numbers in the range have been examined, return the result list.
Why it works
The algorithm checks exactly the two conditions required by the problem definition:
- No digit may be zero.
- Every digit must divide the original number evenly.
Each digit is examined exactly once. If any digit violates either condition, the number is rejected immediately. Therefore, every accepted number is guaranteed to be self-dividing, and every self-dividing number in the range will be included in the output.
Python Solution
from typing import List
class Solution:
def selfDividingNumbers(self, left: int, right: int) -> List[int]:
def is_self_dividing(number: int) -> bool:
current = number
while current > 0:
digit = current % 10
if digit == 0 or number % digit != 0:
return False
current //= 10
return True
result = []
for number in range(left, right + 1):
if is_self_dividing(number):
result.append(number)
return result
The implementation begins with a helper function called is_self_dividing. This function encapsulates the logic for validating a single number.
The variable current is used for digit extraction so that the original number remains unchanged. This is important because divisibility checks must always use the original value.
Inside the while loop:
current % 10extracts the last digit.- The condition
digit == 0rejects numbers containing zero. - The condition
number % digit != 0rejects digits that do not divide evenly.
If either condition fails, the function immediately returns False. This early exit improves efficiency because there is no reason to inspect remaining digits once failure is guaranteed.
The line current //= 10 removes the processed digit.
If the loop finishes successfully, all digits satisfy the requirements, so the function returns True.
The main method iterates through the entire range and appends valid numbers to the result list.
Go Solution
func selfDividingNumbers(left int, right int) []int {
isSelfDividing := func(number int) bool {
current := number
for current > 0 {
digit := current % 10
if digit == 0 || number%digit != 0 {
return false
}
current /= 10
}
return true
}
result := []int{}
for number := left; number <= right; number++ {
if isSelfDividing(number) {
result = append(result, number)
}
}
return result
}
The Go implementation follows the same logic as the Python solution.
A local helper function is used to keep the validation logic clean and reusable. Digits are extracted using % 10 and removed using /= 10.
The result is stored in a slice initialized as an empty slice:
result := []int{}
This ensures the function returns an empty slice rather than nil if no numbers qualify.
Integer overflow is not a concern because the constraints are very small, with values limited to 10^4.
Worked Examples
Example 1
Input:
left = 1
right = 22
We inspect every number from 1 through 22.
| Number | Digits Checked | Valid? | Reason |
|---|---|---|---|
| 1 | 1 | Yes | 1 % 1 == 0 |
| 2 | 2 | Yes | 2 % 2 == 0 |
| 3 | 3 | Yes | 3 % 3 == 0 |
| 4 | 4 | Yes | 4 % 4 == 0 |
| 5 | 5 | Yes | 5 % 5 == 0 |
| 6 | 6 | Yes | 6 % 6 == 0 |
| 7 | 7 | Yes | 7 % 7 == 0 |
| 8 | 8 | Yes | 8 % 8 == 0 |
| 9 | 9 | Yes | 9 % 9 == 0 |
| 10 | 0 | No | Contains zero |
| 11 | 1, 1 | Yes | Divisible by both digits |
| 12 | 2, 1 | Yes | 12 % 2 == 0 and 12 % 1 == 0 |
| 13 | 3 | No | 13 % 3 != 0 |
| 14 | 4 | No | 14 % 4 != 0 |
| 15 | 5, 1 | Yes | Divisible by both digits |
| 16 | 6 | No | 16 % 6 != 0 |
| 17 | 7 | No | 17 % 7 != 0 |
| 18 | 8 | No | 18 % 8 != 0 |
| 19 | 9 | No | 19 % 9 != 0 |
| 20 | 0 | No | Contains zero |
| 21 | 1, 2 | No | 21 % 2 != 0 |
| 22 | 2, 2 | Yes | Divisible by both digits |
Final output:
[1,2,3,4,5,6,7,8,9,11,12,15,22]
Example 2
Input:
left = 47
right = 85
Important checks:
| Number | Digits | Result |
|---|---|---|
| 48 | 4, 8 | Valid |
| 55 | 5, 5 | Valid |
| 66 | 6, 6 | Valid |
| 77 | 7, 7 | Valid |
| 80 | Contains 0 | Invalid |
| 84 | 8, 4 | Invalid because 84 % 8 != 0 |
| 85 | 8, 5 | Invalid because 85 % 8 != 0 |
Final output:
[48,55,66,77]
Complexity Analysis
| Measure | Complexity | Explanation |
|---|---|---|
| Time | O(n * d) | Each number is checked digit by digit |
| Space | O(1) | Only a few variables are used besides the output list |
Where:
n = right - left + 1d = number of digits
Since the maximum value is 10^4, each number contains at most 5 digits. Therefore, the digit-processing cost is effectively constant, making the algorithm very efficient.
Test Cases
from typing import List
class Solution:
def selfDividingNumbers(self, left: int, right: int) -> List[int]:
def is_self_dividing(number: int) -> bool:
current = number
while current > 0:
digit = current % 10
if digit == 0 or number % digit != 0:
return False
current //= 10
return True
result = []
for number in range(left, right + 1):
if is_self_dividing(number):
result.append(number)
return result
solution = Solution()
assert solution.selfDividingNumbers(1, 22) == [1,2,3,4,5,6,7,8,9,11,12,15,22] # Provided example 1
assert solution.selfDividingNumbers(47, 85) == [48,55,66,77] # Provided example 2
assert solution.selfDividingNumbers(1, 1) == [1] # Smallest possible range
assert solution.selfDividingNumbers(10, 10) == [] # Contains zero
assert solution.selfDividingNumbers(11, 11) == [11] # Repeated valid digit
assert solution.selfDividingNumbers(12, 12) == [12] # Multiple valid digits
assert solution.selfDividingNumbers(13, 13) == [] # Non-divisible digit
assert solution.selfDividingNumbers(22, 22) == [22] # Same repeated divisible digit
assert solution.selfDividingNumbers(128, 128) == [128] # Larger valid number
assert solution.selfDividingNumbers(101, 101) == [] # Internal zero digit
assert solution.selfDividingNumbers(999, 1000) == [] # Numbers near upper range with invalid digits
Test Summary
| Test | Why |
|---|---|
1, 22 |
Validates the main example |
47, 85 |
Validates second example |
1, 1 |
Smallest valid input |
10, 10 |
Tests zero digit rejection |
11, 11 |
Tests repeated digits |
12, 12 |
Tests multiple valid digits |
13, 13 |
Tests failed divisibility |
22, 22 |
Tests repeated divisible digits |
128, 128 |
Tests multi-digit valid number |
101, 101 |
Tests embedded zero |
999, 1000 |
Tests upper-range invalid cases |
Edge Cases
One important edge case is numbers containing the digit zero. This is the most common source of bugs because division by zero is undefined. A naive implementation that directly performs number % digit without checking for zero first would crash or raise an exception. The implementation avoids this by immediately rejecting any digit equal to zero before attempting divisibility.
Another important edge case is single-digit numbers. Every number from 1 through 9 is automatically self-dividing because each number divides itself evenly. Some implementations accidentally overcomplicate this case, but the digit-processing loop naturally handles it correctly without any special logic.
A third important edge case is numbers where only one digit fails divisibility. For example, 26 fails because 26 % 6 != 0. The implementation correctly exits early as soon as a failing digit is found. This prevents unnecessary work and ensures correctness even when only one digit invalidates the number.
A fourth subtle edge case involves repeated digits, such as 22 or 55. The algorithm processes each digit independently, even if digits repeat. This guarantees that every occurrence of the digit satisfies the divisibility requirement.
Finally, boundary values near 10^4 are important because they produce the maximum possible digit count. The implementation still works efficiently because each number contains only a handful of digits, so the digit-processing loop remains very small.