Skip to content

728. Self Dividing Numbers

Description

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.

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

Solutions

Solution 1: Simulation

Thinking

The range is at most \(10^4\), and testing a number against its own digits is a few divisions. Enumerating the interval is fine.

A zero digit cannot divide, so those numbers fail immediately; otherwise \(x\) must be divisible by each digit.

Walk digits of \(y=x\); reject on a \(0\) or a failed modulo, otherwise keep \(x\).

We define a function \(\textit{check}(x)\) to determine whether \(x\) is a self-dividing number. The implementation idea of the function is as follows:

We use \(y\) to record the value of \(x\), and then continuously divide \(y\) by \(10\) until \(y\) is \(0\). During this process, we check whether the last digit of \(y\) is \(0\), or whether \(x\) cannot be divided by the last digit of \(y\). If either of these conditions is met, then \(x\) is not a self-dividing number, and we return \(\text{false}\). Otherwise, after traversing all the digits, we return \(\text{true}\).

Finally, we traverse all the numbers in the interval \([\textit{left}, \textit{right}]\), and for each number, we call \(\textit{check}(x)\). If it returns \(\text{true}\), we add this number to the answer array.

The time complexity is \(O(n \times \log_{10} M)\), where \(n\) is the number of elements in the interval \([\textit{left}, \textit{right}]\), and \(M = \textit{right}\), which is the maximum value in the interval.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
class Solution:
    def selfDividingNumbers(self, left: int, right: int) -> List[int]:
        def check(x: int) -> bool:
            y = x
            while y:
                if y % 10 == 0 or x % (y % 10):
                    return False
                y //= 10
            return True

        return [x for x in range(left, right + 1) if check(x)]

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
    public List<Integer> selfDividingNumbers(int left, int right) {
        List<Integer> ans = new ArrayList<>();
        for (int x = left; x <= right; ++x) {
            if (check(x)) {
                ans.add(x);
            }
        }
        return ans;
    }

    private boolean check(int x) {
        for (int y = x; y > 0; y /= 10) {
            if (y % 10 == 0 || x % (y % 10) != 0) {
                return false;
            }
        }
        return true;
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
public:
    vector<int> selfDividingNumbers(int left, int right) {
        auto check = [&](int x) -> bool {
            for (int y = x; y; y /= 10) {
                if (y % 10 == 0 || x % (y % 10)) {
                    return false;
                }
            }
            return true;
        };
        vector<int> ans;
        for (int x = left; x <= right; ++x) {
            if (check(x)) {
                ans.push_back(x);
            }
        }
        return ans;
    }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
func selfDividingNumbers(left int, right int) (ans []int) {
    check := func(x int) bool {
        for y := x; y > 0; y /= 10 {
            if y%10 == 0 || x%(y%10) != 0 {
                return false
            }
        }
        return true
    }
    for x := left; x <= right; x++ {
        if check(x) {
            ans = append(ans, x)
        }
    }
    return
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
function selfDividingNumbers(left: number, right: number): number[] {
    const check = (x: number): boolean => {
        for (let y = x; y; y = Math.floor(y / 10)) {
            if (y % 10 === 0 || x % (y % 10) !== 0) {
                return false;
            }
        }
        return true;
    };
    return Array.from({ length: right - left + 1 }, (_, i) => i + left).filter(check);
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
impl Solution {
    pub fn self_dividing_numbers(left: i32, right: i32) -> Vec<i32> {
        fn check(x: i32) -> bool {
            let mut y = x;
            while y > 0 {
                if y % 10 == 0 || x % (y % 10) != 0 {
                    return false;
                }
                y /= 10;
            }
            true
        }

        (left..=right).filter(|&x| check(x)).collect()
    }
}

Comments