
Problem Statement
Self-dividing numbers are integers that are divisible by each of their digits without leaving any remainder. Specifically, no self-dividing number can contain the digit "0" since division by zero is undefined. The task is to generate a list of all self-dividing numbers that fall within a given range, defined by two integers 'left' and 'right' (both inclusive). For instance, the number 128
qualifies as a self-dividing number because it is evenly divisible by 1
, 2
, and 8
. To solve this problem, you need to check each number in the specified range and determine whether each of its digits evenly divides the number.
Examples
Example 1
Input:
left = 1, right = 22
Output:
[1,2,3,4,5,6,7,8,9,11,12,15,22]
Example 2
Input:
left = 47, right = 85
Output:
[48,55,66,77]
Constraints
1 <= left <= right <= 104
Approach and Intuition
The problem involves checking each number within the specified range to see if it is a self-dividing number. Here is a concise approach to solve the problem:
- Iterate from the 'left' to 'right' boundaries of the range.
- For each number, verify if all its digits divide the number without leaving a remainder.
- Exclude any numbers that contain the digit '0' as they are automatically not self-dividing numbers.
- If a number meets all the criteria, add it to the result list.
- Constraints dictate that checking can be done efficiently since the range has a maximum of 10^4, which is computationally feasible.
- The presence of non-divisible conditions, e.g., digits that result in a non-zero remainder or presence of zero, allows quick exclusion of non-eligible numbers, optimizing the checks slightly.
In the examples provided:
- From
left = 1
toright = 22
yielded numbers such as 1 through 9 (all single-digit numbers are self-dividing) and other specific numbers up to 22 which fulfill the criteria. Notably, numbers like 10, 14, 17, etc., are excluded since they contain digits that don't divide evenly into the number. - From
left = 47
toright = 85
, fewer self-dividing numbers are found due to more digits and complex combinations that fail to be self-dividing, leading to a much smaller list compared to the first example.
Using these steps, one can efficiently filter and compile the list of self-dividing numbers.
Solutions
- Java
- Python
class Solution {
public List<Integer> getSelfDividingNumbers(int start, int end) {
List<Integer> result = new ArrayList<>();
for (int i = start; i <= end; ++i) {
if (isSelfDividing(i)) {
result.add(i);
}
}
return result;
}
public boolean isSelfDividing(int num) {
for (char digit: String.valueOf(num).toCharArray()) {
if (digit == '0' || (num % (digit - '0') != 0)) {
return false;
}
}
return true;
}
}
The Java code defines a class named Solution
that identifies and returns a list of self-dividing numbers between two given integers, inclusive. A self-dividing number is defined as a number that is divisible by every digit it contains, where no digit in the number is zero.
Here's a quick overview of the key components and how they work:
getSelfDividingNumbers(int start, int end)
: This method generates a list of integers. It iterates from the start value to the end value, checking each number to see if it is self-dividing by calling theisSelfDividing(int num)
method.isSelfDividing(int num)
: This method determines if a number is self-dividing. It converts the number to a string, iterates through each character, and checks two conditions:- The digit must not be zero, since division by zero is undefined.
- The number
num
must be divisible by this digit without leaving a remainder.
If both conditions are met for every digit, the number is considered self-dividing, and the method returns true; otherwise, it returns false.
Using these definitions, the code adds only self-dividing numbers to the resulting list, which it returns upon the completion of the iteration through the range. This approach utilizes straightforward control flow and modulo operation to achieve the goal effectively.
class Solution:
# Function to find all self-dividing numbers in a given range
def findSelfDividingNumbers(self, start: int, end: int) -> List[int]:
# Check if the given number is self-dividing
def isSelfDividing(number: int) -> bool:
for digit in str(number):
if digit == '0' or number % int(digit) != 0:
return False
return True
# Accumulate all self-dividing numbers
results = []
for i in range(start, end + 1):
if isSelfDividing(i):
results.append(i)
return results
The solution provided is a Python program that calculates self-dividing numbers within a specified range. Self-dividing numbers are integers that are divisible by each of their digits without leaving a remainder. The implementation involves a main function findSelfDividingNumbers
which iterates through a range of numbers from start
to end
, utilizing a helper function isSelfDividing
to determine if an individual number meets the criteria.
The
isSelfDividing
function works by converting a number into a string to easily access each digit. For each digit in the number, it checks two conditions:- The digit is not zero since division by zero is undefined.
- The original number is divisible by the digit.
If either condition fails, the function returns
False
; otherwise, it continues checking all digits. If all digits pass the test, it returnsTrue
.The main function,
findSelfDividingNumbers
, employs a loop to go through each number fromstart
toend
(inclusive). Each number is passed to theisSelfDividing
function:- If the result is
True
, implying the number is self-dividing, it is added to theresults
list.
- If the result is
The function finally returns the list results
, containing all self-dividing numbers in the given range. This effective approach ensures a clear and organized way to find and list all self-dividing numbers between any two boundaries efficiently.
No comments yet.