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 <= 104This 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.
C++
Java
Python
C#
JavaScript
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.
C++
Java
Python
C#
JavaScript
Time Complexity: O(n*m), where n is the range and m is reduced due to skipping numbers.
Space Complexity: O(1).
| 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. |
LeetCode Self Dividing Numbers Solution Explained - Java • Nick White • 9,447 views views
Watch 9 more video solutions →Practice Self Dividing Numbers with our built-in code editor and test cases.
Practice on FleetCode