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 because128 % 1 == 0
,128 % 2 == 0
, and128 % 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 $\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 |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 |
|
1 2 3 4 5 6 7 8 9 10 11 |
|