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 <= 10⁴

Solutions

Solution 1: Simulation

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.

Python3JavaC++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)]

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;
    }
}

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;
    }
};

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
}

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);
}

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

728. Self Dividing Numbers

Description

Solutions

Solution 1: Simulation

Comments