A self-dividing number is a number that is divisible by every digit it contains.
128 is a self-dividing number because 128 % 1 == 0, 128 % 2 == 0, and 128 % 8 == 0.A self-dividing number is not allowed to contain the digit zero.
Given two integers left and right, return a list of all the self-dividing numbers in the range [left, right] (both inclusive).
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 <= 104Problem Overview: Given a range [left, right], return all numbers where every digit divides the number itself. A valid number cannot contain the digit 0, and each digit must divide the number without remainder.
Approach 1: Brute Force Digit Check (Time: O(n * d), Space: O(1))
Iterate through every number from left to right. For each number, extract digits one by one using modulo and division operations (digit = num % 10, num /= 10). If any digit is 0 or the original number is not divisible by that digit (original % digit != 0), the number is not self dividing. Otherwise continue until all digits are validated. If every digit passes the check, add the number to the result list.
This approach works because digit extraction is constant time per digit and requires no extra data structures. The complexity depends on how many digits each number has, which is d ≈ log10(n). It fits naturally into problems involving math and simple digit manipulation.
Approach 2: Digit Analysis and Skip Non-Divisible (Time: O(n * d), Space: O(1))
This approach still scans the range sequentially but optimizes the digit validation process. While extracting digits, immediately stop processing the number when encountering 0 or a digit that does not divide the number. Early termination avoids unnecessary digit checks for invalid numbers.
Some implementations also skip forward when a 0 digit appears, since any number containing 0 cannot be self dividing. This reduces redundant checks across the range. The algorithm still performs digit extraction using modulo operations but minimizes work for numbers that fail early.
The method relies purely on arithmetic operations, making it efficient and memory-friendly. It frequently appears in beginner-friendly problems involving math and number theory patterns where digits of a number influence its validity.
Recommended for interviews: Interviewers typically expect the digit-check approach with early termination. The brute force version demonstrates that you understand how to iterate through a numeric range and extract digits. The optimized digit analysis shows awareness of pruning unnecessary checks, which keeps the implementation clean and efficient while maintaining O(n * d) time and O(1) space.
This approach involves iterating over each number within the given range. For each number, extract each digit and check if the number is evenly divisible by that digit. If it passes all checks, the number is self-dividing.
This C solution uses a helper function isSelfDividing to check if each number in the range is a self-dividing number. For each number, we repeatedly extract the last digit and check if it divides the original number evenly. The function returns a boolean indicating if a number is self-dividing.
Time Complexity: O(n*m), where n is the range and m is the number of digits in each number.
Space Complexity: O(1) since no extra space is used proportional to input size.
This approach optimizes the check by making a presumption against numbers containing digit zero immediately. Numbers with digit zero are automatically non-self-divisible. For the rest, we still check each digit, but this could reduce the number of required operations.
This C solution skips numbers divisible by 10 entirely, focusing on the rest to identify self-dividing numbers, slightly optimizing computations by reducing unnecessary checks.
Time Complexity: O(n*m), where n is the range and m is reduced due to skipping numbers.
Space Complexity: O(1).
We define a function check(x) to determine whether x is a self-dividing number. The implementation idea of the function is as follows:
We use y to record the value of x, and then continuously divide y by 10 until y is 0. During this process, we check whether the last digit of y is 0, or whether x cannot be divided by the last digit of y. If either of these conditions is met, then x is not a self-dividing number, and we return false. Otherwise, after traversing all the digits, we return true.
Finally, we traverse all the numbers in the interval [left, right], and for each number, we call check(x). If it returns true, we add this number to the answer array.
The time complexity is O(n times log_{10} M), where n is the number of elements in the interval [left, right], and M = right, which is the maximum value in the interval.
| Approach | Complexity |
|---|---|
| Brute Force Approach | Time Complexity: O(n*m), where n is the range and m is the number of digits in each number. |
| Digit Analysis and Skip Non-Divisible | Time Complexity: O(n*m), where n is the range and m is reduced due to skipping numbers. |
| Simulation | — |
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Brute Force Digit Check | O(n * d) | O(1) | Simple implementation when checking each number independently |
| Digit Analysis with Early Break | O(n * d) | O(1) | Preferred approach in interviews due to early pruning of invalid numbers |
Self Dividing Number | Leetcode 728 | Amazon Google Facebook interview question • Super Lazy Coder • 1,416 views views
Watch 9 more video solutions →Practice Self Dividing Numbers with our built-in code editor and test cases.
Practice on FleetCode