algorithm notes: leetcode#728 self dividing numbers

Problem

A self-dividing number is a number that is divisible by every digit it contains.

For example, 128 is a self-dividing number because 128 % 1 == 0, 128 % 2 == 0, and 128 % 8 == 0.

Also, a self-dividing number is not allowed to contain the digit zero.

Given a lower and upper number bound, output a list of every possible self dividing number, including the bounds if possible.

Example 1:

Input:
left = 1, right = 22
Output: [1, 2, 3, 4, 5, 6, 7, 8, 9, 11, 12, 15, 22]

Note:

• The boundaries of each input argument are 1 <= left <= right <= 10000.

Solution

Basic idea

Solve it with brute force. Iterate each number between left and right. For each number, convert it to string and check whether it contains ‘0’. If it contains, ignore it. If not, iterate each digit and check whether the number can be divided by all digits.

Python implementation

1
2
3
4
5
6
7
8
9

class :
    def selfDividingNumbers(self, left, right):
        """
        :type left: int
        :type right: int
        :rtype: List[int]
        """
        return [num for num in range(left, right+1)
                if '0' not in str(num) and all(num % int(c) == 0 for c in str(num))]

Java implementation

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

class  {
    public List<Integer> selfDividingNumbers(int left, int right) {
        List<Integer> ans = new ArrayList<>();
        
        for(int num = left; num <= right; num++){
            boolean flag = true;
            for(char c : Integer.toString(num).toCharArray()){
                if(c == '0' || num % (c - '0') != 0){
                    flag = false;
                    break;
                }
            }
            if(flag){ ans.add(num); }
        }
        return ans;
    }
}

Time complexity analysis

O(L). L is the number of integers between left and right. We need to iterate integers from left to right.

Space complexity analysis

O(1).

Link

728. Self Dividing Numbers
728. 自除数
(中文版) 算法笔记: 力扣#728 自除数