Problem statement

A self-dividing number is a number that is divisible by every digit it contains. For example, 128 is self-dividing because 128 % 1 == 0, 128 % 2 == 0 and 128 % 8 == 0. A self-dividing number is never allowed to contain the digit zero.

Given two integers left and right, return a sorted list of every self-dividing number in the inclusive range [left, right].

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]

Example 3

Input: left = 10, right = 10
Output: []
Explanation: 10 contains a zero.

Constraints

• 1 <= left <= right <= 20000
• right - left <= 120

Hints for Self Dividing Numbers

1. Hint 1

   Test each number in the range independently — the range is small.

2. Hint 2

   Peel the digits of the candidate while keeping the original value to divide by.

3. Hint 3

   A zero digit disqualifies immediately; do not attempt the division.

How to solve Self Dividing Numbers

The range is small, so test each candidate independently: peel its digits and reject at the first zero or non-dividing digit.

Approach

1. For each n in [left, right], copy it to x and assume ok = true.
2. While x > 0: take d = x % 10; if d == 0 or n % d != 0, mark not ok and stop; else drop the digit.
3. Collect every n that passed.

Why it works

Iterating the range in order produces a sorted result for free, and short-circuiting on the first failing digit keeps each test cheap.

Complexity

• Time — O((right - left) · digits)
• Space — O(1) beyond the output

Pitfalls

• Test for the zero digit before dividing, or you divide by zero.
• Divide the original n, not the shrinking x.

Reference solution

Python

def selfDividingNumbers(left: int, right: int):
    out = []
    for n in range(left, right + 1):
        x, ok = n, True
        while x > 0:
            d = x % 10
            if d == 0 or n % d != 0:
                ok = False
                break
            x //= 10
        if ok:
            out.append(n)
    return out

Java

public static int[] selfDividingNumbers(int left, int right) {
    List<Integer> out = new ArrayList<>();
    for (int n = left; n <= right; n++) {
        int x = n;
        boolean ok = true;
        while (x > 0) {
            int d = x % 10;
            if (d == 0 || n % d != 0) { ok = false; break; }
            x /= 10;
        }
        if (ok) out.add(n);
    }
    int[] res = new int[out.size()];
    for (int i = 0; i < res.length; i++) res[i] = out.get(i);
    return res;
}

C++

vector<int> selfDividingNumbers(int left, int right) {
    vector<int> out;
    for (int n = left; n <= right; n++) {
        int x = n;
        bool ok = true;
        while (x > 0) {
            int d = x % 10;
            if (d == 0 || n % d != 0) { ok = false; break; }
            x /= 10;
        }
        if (ok) out.push_back(n);
    }
    return out;
}

JavaScript

var selfDividingNumbers = function(left, right) {
    const out = [];
    for (let n = left; n <= right; n++) {
        let x = n, ok = true;
        while (x > 0) {
            const d = x % 10;
            if (d === 0 || n % d !== 0) { ok = false; break; }
            x = Math.floor(x / 10);
        }
        if (ok) out.push(n);
    }
    return out;
};

Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

More math problems

• Multiply Two Linked Lists Easy
• Convert Binary Number in a Linked List to Integer Easy
• Check if Any Element Has Prime Frequency Easy
• Convert Date to Binary Easy
• Count Ways to Tile a 2 x N Floor Easy
• Find Nth Root of M Easy