LeetCode 0728. Self Dividing Numbers Solution in Java, C++, Python & More | Explanation + Code

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

We define a function 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 false. Otherwise, after traversing all the digits, we return true.

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

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

PythonJavaC++GoTypeScriptRust

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)](code-box)

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; } }(code-box)

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; } };(code-box)

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 }(code-box)

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); }(code-box)

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() } }(code-box)