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.


TA 👨‍🏫