Leetcode 728. Self Dividing Numbers
Problem Explanation
The problem involves finding all the self-dividing numbers within a given range. A self dividing number is a number that is divisible by every digit it contains. For instance, considering the number 128, it is a self-dividing number as 128 % 1 == 0, 128 % 2 == 0, and 128 % 8 == 0.
Note that a self-dividing number is not allowed to contain the digit zero. Given a lower and upper number bound, the task is to find and output a list of every possible self dividing number, including the bounds if possible.
Example Walkthrough
Let's consider an example to understand the problem better.
Input: left = 1 , right = 22
The numbers from 1 to 22 are [1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22]
Checking each number, the self-dividing numbers are [1,2,3,4,5,6,7,8,9,11,12,15,22]
So, the output would be [1, 2, 3, 4, 5, 6, 7, 8, 9, 11, 12, 15, 22]
Solution Approach
The solution involves a simple iteration from the lower bound to the higher bound of the given range. For each number, it checks if it's a self-dividing number. Then, this process is repeated until we have assessed every number in the range. If a number is self-dividing, it is included in the output list.
Solutions
Python Solution
1 2python 3class Solution: 4 def selfDividingNumbers(self, left: int, right: int): 5 def isSelfDividing(n: int) -> bool: 6 for digit in str(n): 7 if digit=='0' or n % int(digit)!=0: 8 return False 9 return True 10 11 res = [] 12 for n in range(left, right + 1): 13 if isSelfDividing(n): 14 res.append(n) 15 return res
Java Solution
1
2java
3class Solution {
4 public List<Integer> selfDividingNumbers(int left, int right) {
5 List<Integer> res = new ArrayList<>();
6 for (int num = left; num <= right; ++num)
7 if (isSelfDividing(num)) res.add(num);
8 return res;
9 }
10
11 private boolean isSelfDividing(int n) {
12 for (char c : String.valueOf(n).toCharArray())
13 if (c == '0' || n % (c - '0') > 0)
14 return false;
15 return true;
16 }
17}
JavaScript Solution
1 2javascript 3var selfDividingNumbers = function(left, right) { 4 const output = []; 5 for(let i = left; i <= right; i++){ 6 if(i.toString().split('').every((char) => i % parseInt(char) === 0)) output.push(i); 7 } 8 return output; 9};
C++ Solution
1
2c++
3class Solution {
4public:
5 vector<int> selfDividingNumbers(int left, int right) {
6 vector<int> result;
7 for( int i = left; i <= right; i++)
8 if(isDividingNumber(i)) result.push_back(i);
9 return result;
10 }
11
12private:
13 bool isDividingNumber(int num){
14 for(int n = num; n > 0; n /= 10)
15 if(!( n % 10) || num % (n % 10)) return false;
16 return true;
17 }
18};
C# Solution
1
2csharp
3public class Solution {
4 public IList<int> SelfDividingNumbers(int left, int right) {
5 List<int> result = new List<int>();
6 for(int i = left; i <= right; i++){
7 if(IsSelfDividing(i)) result.Add(i);
8 }
9 return result;
10 }
11
12 private bool IsSelfDividing(int num){
13 foreach(char c in num.ToString()){
14 int digit = c - '0';
15 if(digit == 0 || num % digit != 0)
16 return false;
17 }
18 return true;
19 }
20}
These solutions involve creating a helper function to determine if a number is a self-dividing number then, in the main function, iterating from the left bound to the right, adding every self-dividing number to the list of results.
It begins by defining a boolean method isSelfDividing that takes an integer num as an argument. It returns false if n is not a self-dividing number.
The algorithm for isSelfDividing works by first converting the integer num to a string using the built-in conversion methods in each programming language. Then it iterates over each character in the string.
If any character in the string is a '0', or if the input number is not divisible by the integer value of the character, then the number is not self-dividing, and the function returns false.
Otherwise, if all characters in the string pass the check, the function returns true, indicating that the number is self-dividing.
Back in the main function, a loop is initiated starting from the lower bound to the upper bound where the helper function is invoked on each iteration. If the number is a self-dividing number, it's added to the list, and finally, the list of all self-dividing numbers is returned.
This solution has a time complexity of O(D), where D is the number of integers in the range from lower bound to upper bound, and space complexity is also O(D), D being the number of self-dividing numbers.
Got a question?ย Ask the Teaching Assistantย anything you don't understand.
Still not clear? Ask in the Forum, ย Discordย orย Submitย the part you don't understand to our editors.