LeetCode 728: Self Dividing Numbers (Digit-by-Digit Validity Check)
LeetCode 728MathDigit ProcessingSimulationToday we solve LeetCode 728 - Self Dividing Numbers.
Source: https://leetcode.com/problems/self-dividing-numbers/
English
Problem Summary
Given integers left and right, return all self-dividing numbers in this inclusive range. A self-dividing number contains no digit 0, and every digit must divide the number evenly.
Key Insight
For each candidate number n, repeatedly extract its last digit by % 10. If any digit is 0 or n % digit != 0, it fails immediately.
Brute Force and Limitations
String conversion also works, but digit arithmetic is more direct and avoids extra conversions.
Optimal Algorithm Steps
1) Iterate x from left to right.
2) Set cur = x and inspect digits one by one.
3) If digit is zero or not a divisor of x, mark invalid.
4) If all digits pass, append x to answer.
Complexity Analysis
Let R = right - left + 1, and each number has at most D digits.
Time: O(R · D).
Space: O(1) extra (excluding output).
Common Pitfalls
- Forgetting digit 0 is always invalid.
- Accidentally checking divisibility against changing cur instead of original x.
- Missing inclusive boundaries.
Reference Implementations (Java / Go / C++ / Python / JavaScript)
class Solution {
public List<Integer> selfDividingNumbers(int left, int right) {
List<Integer> ans = new ArrayList<>();
for (int x = left; x <= right; x++) {
if (isSelfDividing(x)) {
ans.add(x);
}
}
return ans;
}
private boolean isSelfDividing(int x) {
int cur = x;
while (cur > 0) {
int d = cur % 10;
if (d == 0 || x % d != 0) return false;
cur /= 10;
}
return true;
}
}func selfDividingNumbers(left int, right int) []int {
ans := []int{}
for x := left; x <= right; x++ {
if isSelfDividing(x) {
ans = append(ans, x)
}
}
return ans
}
func isSelfDividing(x int) bool {
cur := x
for cur > 0 {
d := cur % 10
if d == 0 || x%d != 0 {
return false
}
cur /= 10
}
return true
}class Solution {
public:
vector<int> selfDividingNumbers(int left, int right) {
vector<int> ans;
for (int x = left; x <= right; ++x) {
if (isSelfDividing(x)) ans.push_back(x);
}
return ans;
}
private:
bool isSelfDividing(int x) {
int cur = x;
while (cur > 0) {
int d = cur % 10;
if (d == 0 || x % d != 0) return false;
cur /= 10;
}
return true;
}
};class Solution:
def selfDividingNumbers(self, left: int, right: int) -> list[int]:
def ok(x: int) -> bool:
cur = x
while cur > 0:
d = cur % 10
if d == 0 or x % d != 0:
return False
cur //= 10
return True
return [x for x in range(left, right + 1) if ok(x)]var selfDividingNumbers = function(left, right) {
const ans = [];
const ok = (x) => {
let cur = x;
while (cur > 0) {
const d = cur % 10;
if (d === 0 || x % d !== 0) return false;
cur = Math.floor(cur / 10);
}
return true;
};
for (let x = left; x <= right; x++) {
if (ok(x)) ans.push(x);
}
return ans;
};中文
题目概述
给定区间 [left, right]，返回其中所有自除数。自除数要求：不包含数字 0，并且每一位数字都能整除该数本身。
核心思路
对每个候选数 x，通过 % 10 和 / 10 逐位取出数字。只要出现 0 或 x % digit != 0，立刻判失败。
暴力解法与不足
把数字转字符串再遍历字符也能做，但整数位运算更直接、开销更低。
最优算法步骤
1）遍历区间中的每个整数 x。
2）令 cur = x，逐位检查。
3）若某位为 0 或不能整除 x，判定不合法。
4）若所有位都合法，则加入答案。
复杂度分析
设区间长度为 R，每个数最多 D 位。
时间复杂度：O(R · D)。
额外空间复杂度：O(1)（不计输出）。
常见陷阱
- 忘记将数字 0 直接判为不合法位。
- 用变化后的 cur 去做整除判断，导致逻辑错误。
- 忽略区间是闭区间（包含左右端点）。
多语言参考实现（Java / Go / C++ / Python / JavaScript）
class Solution {
public List<Integer> selfDividingNumbers(int left, int right) {
List<Integer> ans = new ArrayList<>();
for (int x = left; x <= right; x++) {
if (isSelfDividing(x)) {
ans.add(x);
}
}
return ans;
}
private boolean isSelfDividing(int x) {
int cur = x;
while (cur > 0) {
int d = cur % 10;
if (d == 0 || x % d != 0) return false;
cur /= 10;
}
return true;
}
}func selfDividingNumbers(left int, right int) []int {
ans := []int{}
for x := left; x <= right; x++ {
if isSelfDividing(x) {
ans = append(ans, x)
}
}
return ans
}
func isSelfDividing(x int) bool {
cur := x
for cur > 0 {
d := cur % 10
if d == 0 || x%d != 0 {
return false
}
cur /= 10
}
return true
}class Solution {
public:
vector<int> selfDividingNumbers(int left, int right) {
vector<int> ans;
for (int x = left; x <= right; ++x) {
if (isSelfDividing(x)) ans.push_back(x);
}
return ans;
}
private:
bool isSelfDividing(int x) {
int cur = x;
while (cur > 0) {
int d = cur % 10;
if (d == 0 || x % d != 0) return false;
cur /= 10;
}
return true;
}
};class Solution:
def selfDividingNumbers(self, left: int, right: int) -> list[int]:
def ok(x: int) -> bool:
cur = x
while cur > 0:
d = cur % 10
if d == 0 or x % d != 0:
return False
cur //= 10
return True
return [x for x in range(left, right + 1) if ok(x)]var selfDividingNumbers = function(left, right) {
const ans = [];
const ok = (x) => {
let cur = x;
while (cur > 0) {
const d = cur % 10;
if (d === 0 || x % d !== 0) return false;
cur = Math.floor(cur / 10);
}
return true;
};
for (let x = left; x <= right; x++) {
if (ok(x)) ans.push(x);
}
return ans;
};
Comments