Self Dividing Numbers

easy math number theory

Problem

Given two integers left and right, return a list of all self-dividing numbers in the inclusive range. A self-dividing number is divisible by each of its digits and contains no zero digits.

Inputleft=1, right=22

Output[1,2,3,4,5,6,7,8,9,11,12,15,22]

Numbers like 10 are excluded because they contain a zero digit.

input

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

function selfDividingNumbers(left, right) {
  const res = [];
  for (let n = left; n <= right; n++) {
    let x = n, ok = true;
    while (x) {
      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;
}

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

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

Explanation

A self-dividing number must be divisible by every one of its own digits, and it can't contain a 0 (you can't divide by zero). We simply test each number in the range one by one.

For a candidate n, we peel its digits with d = x % 10 and x //= 10. For each digit we check two things: is it 0, or does n % d != 0? If either fails, n is rejected and we stop checking it early.

If every digit passes, n is self-dividing and we add it to the result list. We repeat across the whole inclusive range [left, right].

Example: take 12. Its digits are 2 and 1. 12 % 2 == 0 and 12 % 1 == 0, so it qualifies. But 10 contains a 0 digit, so it's immediately rejected.

For left=1, right=22 this collects [1,2,3,4,5,6,7,8,9,11,12,15,22]. The approach is just a direct digit check on each number, which is plenty fast for these ranges.

Time: O((R - L) * log R) Space: O(1)