Self Dividing Numbers
EasyPrompt
A self-dividing number is a number that is divisible by every digit it contains.
- For example,
128is a self-dividing number because128 % 1 == 0,128 % 2 == 0, and128 % 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 <= 104
Approaches
2 approaches with complexity analysis and trade-offs.
This approach iterates through each number in the given range [left, right]. For each number, it converts the number to a string to easily access its digits. It then checks if the number is divisible by each of its digits.
Algorithm
- Initialize an empty list
ansto store the self-dividing numbers. - Iterate through each number
ifromlefttoright. - For each number
i, check if it is a self-dividing number using a helper function. - Helper function
isSelfDividing(num):- Convert the number
numto a strings. - Iterate through each character
cof the strings. - Convert the character
cto an integerdigit. - If
digitis 0, returnfalse. - If
numis not divisible bydigit(i.e.,num % digit != 0), returnfalse. - If the loop completes without returning, it means the number is self-dividing, so return
true.
- Convert the number
- If the helper function returns
truefori, addito theanslist. - After the loop finishes, return the
anslist.
Walkthrough
The algorithm involves a loop that goes from left to right. Inside the loop, for each number num, we first convert it into its string representation. We then iterate through each character of the string. Each character is converted back to an integer digit. Two conditions are checked for each digit:
- If the digit is 0, the number is not self-dividing.
- If the original number
numis not divisible by the digit, it's not self-dividing.
If a number fails either of these checks, we stop processing it and move to the next number in the range. If a number passes the divisibility check for all its digits, it is added to our result list. Finally, the list of self-dividing numbers is returned.
import java.util.ArrayList;import java.util.List; class Solution { public List<Integer> selfDividingNumbers(int left, int right) { List<Integer> result = new ArrayList<>(); for (int i = left; i <= right; i++) { if (isSelfDividing(i)) { result.add(i); } } return result; } private boolean isSelfDividing(int num) { String s = String.valueOf(num); for (char c : s.toCharArray()) { int digit = c - '0'; if (digit == 0) { return false; // Cannot contain digit 0 } if (num % digit != 0) { return false; // Not divisible by one of its digits } } return true; }}Complexity
Time
O(D * log(R)), where D is the number of integers in the range `[left, right]` (i.e., `right - left + 1`), and R is the value of `right`. For each number, we convert it to a string and iterate through its digits. The number of digits in a number `n` is proportional to `log10(n)`. Since `right` is the upper bound, the complexity is dominated by checking numbers near `right`.
Space
O(log(R)) for auxiliary space, excluding the output list. This space is used to store the string representation of a number. The output list itself can take up to O(D) space in the worst case, where D is the number of elements in the range.
Trade-offs
Pros
Conceptually simple and easy to implement.
Directly translates the problem definition into code.
Cons
Involves type conversions (integer to string, character to integer), which can be less efficient than pure arithmetic operations.
Uses slightly more memory due to the creation of string objects for each number.
This approach is an optimization over the string conversion method. It avoids strings altogether and uses mathematical operations (modulo and division) to extract the digits of each number. This is generally faster and more memory-efficient.
Algorithm
- Initialize an empty list
ans. - Iterate through each number
ifromlefttoright. - For each number
i, check if it is a self-dividing number using a helper function. - Helper function
isSelfDividing(num):- Create a temporary copy of the number,
temp = num. - Loop as long as
temp > 0. - Extract the last digit using the modulo operator:
digit = temp % 10. - If
digitis 0, returnfalse. - If the original number
numis not divisible bydigit(i.e.,num % digit != 0), returnfalse. - Remove the last digit from
tempby integer division:temp /= 10. - If the loop completes, return
true.
- Create a temporary copy of the number,
- If the helper function returns
truefori, addito theanslist. - Return the
anslist.
Walkthrough
Similar to the first approach, we iterate through every number num from left to right. To check if num is self-dividing, we use a loop that processes the number's digits without converting it to a string. We use a temporary variable, say currentNum, initialized to num. In a while loop that continues as long as currentNum > 0, we extract the last digit using the modulo operator: digit = currentNum % 10. We then check the same two conditions:
- If
digitis 0, the number is not self-dividing. - If the original number
numis not divisible bydigit, it's not self-dividing.
If either check fails, we immediately know num is not self-dividing and can move to the next number in the range. After checking a digit, we remove it from currentNum by integer division: currentNum = currentNum / 10. If the while loop completes for all digits, the number is self-dividing and is added to the result list.
import java.util.ArrayList;import java.util.List; class Solution { public List<Integer> selfDividingNumbers(int left, int right) { List<Integer> result = new ArrayList<>(); for (int i = left; i <= right; i++) { if (isSelfDividing(i)) { result.add(i); } } return result; } private boolean isSelfDividing(int num) { int temp = num; while (temp > 0) { int digit = temp % 10; if (digit == 0) { return false; // Cannot contain digit 0 } if (num % digit != 0) { return false; // Not divisible by one of its digits } temp /= 10; } return true; }}Complexity
Time
O(D * log(R)), where D is the number of integers in the range `[left, right]` and R is the value of `right`. The logic is the same as the previous approach, but arithmetic operations are generally faster than string conversions, leading to better practical performance.
Space
O(1) for auxiliary space, excluding the output list. This method only uses a few integer variables for its calculations, making it very memory-efficient. The output list can still take up to O(D) space.
Trade-offs
Pros
More efficient in both time and space compared to the string conversion method.
Avoids the overhead of creating and garbage-collecting string objects.
Cons
The logic, while simple, might be slightly less direct for those more comfortable with string manipulation.
Solutions
Solution
class Solution { public List < Integer > selfDividingNumbers ( int left , int right ) { List < Integer > ans = new ArrayList <>(); for ( int i = left ; i <= right ; ++ i ) { if ( check ( i )) { ans . add ( i ); } } return ans ; } private boolean check ( int num ) { for ( int t = num ; t != 0 ; t /= 10 ) { int x = t % 10 ; if ( x == 0 || num % x != 0 ) { return false ; } } return true ; } }class Solution { public: vector < int > selfDividingNumbers ( int left , int right ) { vector < int > ans ; for ( int i = left ; i <= right ; ++ i ) if ( check ( i )) ans . push_back ( i ); return ans ; } bool check ( int num ) { for ( int t = num ; t ; t /= 10 ) { int x = t % 10 ; if ( x == 0 || num % x ) return false ; } return true ; } };class Solution : def selfDividingNumbers ( self , left : int , right : int ) -> List [ int ]: return [ num for num in range ( left , right + 1 ) if all ( i != '0' and num % int ( i ) == 0 for i in str ( num )) ]Video walkthrough
Newsletter
One sharp idea, every week
System design and interview prep — short enough to finish.
No spam. Unsubscribe anytime.
Practice
Same difficulty — related problems to reinforce the pattern.