Problem

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 theself-dividing numbers in the range [left, right] (both inclusive).

Examples

Example 1

1
2

Input: left = 1, right = 22
Output: [1,2,3,4,5,6,7,8,9,11,12,15,22]

Example 2

1
2

Input: left = 47, right = 85
Output: [48,55,66,77]

Constraints

  • 1 <= left <= right <= 10^4

Solution

Method 1 - Brute Force Digit Check

Intuition

For each number in the range, check if all its digits are nonzero and divide the number itself. If so, include it in the answer. This is efficient enough for the given constraints.

Approach

  1. Iterate from left to right.
  2. For each number, check each digit:
    • If the digit is zero or does not divide the number, skip.
    • Otherwise, if all digits pass, add to result.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18

#include <vector>
using namespace std;
class Solution {
public:
    vector<int> selfDividingNumbers(int left, int right) {
        vector<int> res;
        for (int n = left; n <= right; ++n) {
            int x = n, ok = 1;
            while (x) {
                int d = x % 10;
                if (d == 0 || n % d != 0) { ok = 0; break; }
                x /= 10;
            }
            if (ok) res.push_back(n);
        }
        return res;
    }
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18

func selfDividingNumbers(left int, right int) []int {
    res := []int{}
    for n := left; n <= right; n++ {
        x, ok := n, true
        for x > 0 {
            d := x % 10
            if d == 0 || n%d != 0 {
                ok = false
                break
            }
            x /= 10
        }
        if ok {
            res = append(res, n)
        }
    }
    return res
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17

import java.util.*;
class Solution {
    public List<Integer> selfDividingNumbers(int left, int right) {
        List<Integer> res = 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) res.add(n);
        }
        return res;
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16

class Solution {
    fun selfDividingNumbers(left: Int, right: Int): List<Int> {
        val res = mutableListOf<Int>()
        for (n in left..right) {
            var x = n
            var ok = true
            while (x > 0) {
                val d = x % 10
                if (d == 0 || n % d != 0) { ok = false; break }
                x /= 10
            }
            if (ok) res.add(n)
        }
        return res
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14

def selfDividingNumbers(left, right):
    res = []
    for n in range(left, right+1):
        x = n
        ok = True
        while x > 0:
            d = x % 10
            if d == 0 or n % d != 0:
                ok = False
                break
            x //= 10
        if ok:
            res.append(n)
    return res
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14

pub fn self_dividing_numbers(left: i32, right: i32) -> Vec<i32> {
    let mut res = Vec::new();
    for n in left..=right {
        let mut x = n;
        let mut ok = true;
        while x > 0 {
            let d = x % 10;
            if d == 0 || n % d != 0 { ok = false; break; }
            x /= 10;
        }
        if ok { res.push(n); }
    }
    res
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13

function selfDividingNumbers(left: number, right: number): number[] {
    const res: number[] = [];
    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) res.push(n);
    }
    return res;
}

Complexity

  • ⏰ Time complexity: O(N * D) where N = right - left + 1, D = number of digits per number (at most 5)
  • 🧺 Space complexity: O(N) for the result list