Problem Description

The "Self Dividing Numbers" problem asks you to find all numbers within a given range such that each number is divisible by every one of its digits. Specifically, given two integers left and right, you must return a list of all self-dividing numbers in the inclusive range [left, right].

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. If the number contains the digit 0, it is not self-dividing (since division by zero is not allowed).

Constraints:

• 1 <= left <= right <= 10,000
• Each number in the range must be checked individually.
• Zero digits invalidate a number (since division by zero is undefined).

Thought Process

When first approaching this problem, it's natural to think about iterating through every number in the specified range and checking if each number meets the self-dividing criteria. The brute-force approach would be to examine every digit of each number and ensure that the number is divisible by each digit and that none of its digits are zero.

However, we can optimize our approach by terminating the check early if we encounter a zero digit or a digit that does not divide the number evenly. This avoids unnecessary checks for numbers that are already invalid.

The problem does not require us to store or reuse any intermediate results, so a simple iteration and digit-checking method is both effective and efficient for the given constraints.

Solution Approach

Let's break down the steps to solve the Self Dividing Numbers problem:

1. Iterate through the range: Loop through every integer num from left to right (inclusive).
2. Check each digit: For each number, extract its digits one by one (usually by repeatedly taking num % 10 and num // 10).
3. Validate digits:
   • If any digit is zero, immediately discard the number (since division by zero is not allowed).
   • If the number is not divisible by a digit, discard it.
4. Collect valid numbers: If a number passes all digit checks, add it to the result list.

This approach is straightforward and leverages early termination to avoid unnecessary computation. Since each number is checked independently, the process is simple to implement and understand.

Example Walkthrough

Let's walk through an example where left = 21 and right = 23:

• Number 21:
  • Digits: 2 and 1
  • 21 % 2 = 1 (not divisible) → Not self-dividing
• Number 22:
  • Digits: 2 and 2
  • 22 % 2 = 0 (divisible), 22 % 2 = 0 (divisible) → Self-dividing
  • Add 22 to the result
• Number 23:
  • Digits: 2 and 3
  • 23 % 2 = 1 (not divisible) → Not self-dividing

Final output: [22]

Time and Space Complexity

Brute-force approach:

• For each number between left and right (let's call the count n), we check all its digits (at most 5 digits for numbers up to 10,000).
• Time Complexity: O(n * d), where d is the maximum number of digits (at most 5).
• Space Complexity: O(1) extra space (excluding the output list).

• Early termination reduces average checks per number but does not change the worst-case complexity.
• No additional data structures are required.

Summary

The Self Dividing Numbers problem is elegantly solved by iterating through the given range and checking each number's digits for divisibility and the absence of zero. The algorithm is efficient for the input constraints, simple to implement, and leverages early termination for performance. The key insight is that each number can be checked independently using straightforward digit operations.

Code Implementation

class Solution:
    def selfDividingNumbers(self, left: int, right: int) -> list[int]:
        def is_self_dividing(num):
            for digit in str(num):
                if digit == '0' or num % int(digit) != 0:
                    return False
            return True

        return [num for num in range(left, right + 1) if is_self_dividing(num)]
      

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

class Solution {
    public List<Integer> selfDividingNumbers(int left, int right) {
        List<Integer> result = new ArrayList<>();
        for (int num = left; num <= right; num++) {
            if (isSelfDividing(num)) {
                result.add(num);
            }
        }
        return result;
    }
    
    private boolean isSelfDividing(int num) {
        int n = num;
        while (n > 0) {
            int digit = n % 10;
            if (digit == 0 || num % digit != 0) {
                return false;
            }
            n /= 10;
        }
        return true;
    }
}
      

/**
 * @param {number} left
 * @param {number} right
 * @return {number[]}
 */
var selfDividingNumbers = function(left, right) {
    const result = [];
    for (let num = left; num <= right; num++) {
        let n = num;
        let isSelfDividing = true;
        while (n > 0) {
            let digit = n % 10;
            if (digit === 0 || num % digit !== 0) {
                isSelfDividing = false;
                break;
            }
            n = Math.floor(n / 10);
        }
        if (isSelfDividing) result.push(num);
    }
    return result;
};