Watch 10 video solutions for Self Dividing Numbers, a easy level problem involving Math. This walkthrough by Super Lazy Coder has 1,416 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
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.
| 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 |