728. Self Dividing Numbers
Model: qwen2.5-coder:14b
Topics: Math
FAANG asked: 0
Acceptance rate: 75.6%
Problem Breakdown
The problem asks us to identify self-dividing numbers within a given range [left, right]. A self-dividing number is defined as a number that is divisible by each of its digits and does not contain the digit zero. The task is to return a list of all such numbers within the specified bounds.
Inputs:
- Two integers,
leftandright, representing the lower and upper bounds of the range.
Outputs:
- A list of self-dividing numbers within the range
[left, right].
Implicit Constraints or Edge Cases:
- The input values are constrained to
1 <= left <= right <= 10000. - Single-digit numbers are trivially self-dividing.
- Numbers containing zero cannot be self-dividing.
Intuition
A brute-force approach would involve iterating through each number in the range and checking if it is self-dividing by examining each digit. This method is straightforward but inefficient, especially for larger ranges, as it involves multiple modulus operations per number.
To improve efficiency, we can leverage the fact that a number containing zero cannot be self-dividing. Thus, we can skip such numbers early in our checks. Additionally, we can convert numbers to strings to easily iterate over their digits and perform divisibility checks.
Approach
- Initialize an empty list to store the self-dividing numbers.
- Iterate through each number from
lefttoright. - For each number:
- Convert it to a string to check its digits.
- If any digit is zero, skip this number.
- Check if the number is divisible by each of its digits.
- If all checks pass, add the number to the list.
- Return the list of self-dividing numbers.
Complexity Analysis
- Time Complexity: O(n * d), where
nis the count of numbers in the range[left, right], anddis the average number of digits in these numbers. In the worst case, this could be O(4000 * 5) = O(20000), given the constraints. - Space Complexity: O(n), where
nis the count of self-dividing numbers found within the range.
Solution
def selfDividingNumbers(left: int, right: int) -> List[int]:
result = []
for num in range(left, right + 1):
str_num = str(num)
if '0' in str_num:
continue
is_self_dividing = True
for digit in str_num:
if num % int(digit) != 0:
is_self_dividing = False
break
if is_self_dividing:
result.append(num)
return result
Edge Cases Handled
- Single-digit numbers: All single-digit numbers are self-dividing and will be included in the output.
- Numbers containing zero: These numbers are skipped early due to the presence of ‘0’ in their string representation.
- Bounds inclusion: The problem specifies that bounds should be included if they are self-dividing, which is handled by iterating from
lefttoright + 1.