# Self Dividing Numbers
**Difficulty:** EASY
[External](https://leetcode.com/problems/self-dividing-numbers)
Canonical: https://scaleengineer.com/dsa/problems/self-dividing-numbers
**Patterns:** [Math](https://scaleengineer.com/dsa/patterns/math)
**Companies:** [Epic Systems](https://scaleengineer.com/companies/epic-systems)
---
## 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 the **self-dividing numbers** in the range_ `[left, right]` (both **inclusive**).

**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]

**Constraints:**

* `1 <= left <= right <= 104`

# Approaches
## Brute-Force with String Conversion
This approach iterates through each number in the given range `[left, right]`. For each number, it converts the number to a string to easily access its digits. It then checks if the number is divisible by each of its digits.
**Time:** O(D * log(R)), where D is the number of integers in the range `[left, right]` (i.e., `right - left + 1`), and R is the value of `right`. For each number, we convert it to a string and iterate through its digits. The number of digits in a number `n` is proportional to `log10(n)`. Since `right` is the upper bound, the complexity is dominated by checking numbers near `right`. · **Space:** O(log(R)) for auxiliary space, excluding the output list. This space is used to store the string representation of a number. The output list itself can take up to O(D) space in the worst case, where D is the number of elements in the range.
**Pros:** Conceptually simple and easy to implement.; Directly translates the problem definition into code.
**Cons:** Involves type conversions (integer to string, character to integer), which can be less efficient than pure arithmetic operations.; Uses slightly more memory due to the creation of string objects for each number.
### Explanation
The algorithm involves a loop that goes from `left` to `right`. Inside the loop, for each number `num`, we first convert it into its string representation. We then iterate through each character of the string. Each character is converted back to an integer digit. Two conditions are checked for each digit:

1.  If the digit is 0, the number is not self-dividing.
2.  If the original number `num` is not divisible by the digit, it's not self-dividing.

If a number fails either of these checks, we stop processing it and move to the next number in the range. If a number passes the divisibility check for all its digits, it is added to our result list. Finally, the list of self-dividing numbers is returned.

```java
import java.util.ArrayList;
import java.util.List;

class Solution {
    public List<Integer> selfDividingNumbers(int left, int right) {
        List<Integer> result = new ArrayList<>();
        for (int i = left; i <= right; i++) {
            if (isSelfDividing(i)) {
                result.add(i);
            }
        }
        return result;
    }

    private boolean isSelfDividing(int num) {
        String s = String.valueOf(num);
        for (char c : s.toCharArray()) {
            int digit = c - '0';
            if (digit == 0) {
                return false; // Cannot contain digit 0
            }
            if (num % digit != 0) {
                return false; // Not divisible by one of its digits
            }
        }
        return true;
    }
}
```
### Algorithm
- Initialize an empty list `ans` to store the self-dividing numbers.
- Iterate through each number `i` from `left` to `right`.
- For each number `i`, check if it is a self-dividing number using a helper function.
- **Helper function `isSelfDividing(num)`:**
  - Convert the number `num` to a string `s`.
  - Iterate through each character `c` of the string `s`.
  - Convert the character `c` to an integer `digit`.
  - If `digit` is 0, return `false`.
  - If `num` is not divisible by `digit` (i.e., `num % digit != 0`), return `false`.
  - If the loop completes without returning, it means the number is self-dividing, so return `true`.
- If the helper function returns `true` for `i`, add `i` to the `ans` list.
- After the loop finishes, return the `ans` list.

## Brute-Force with Arithmetic Operations
This approach is an optimization over the string conversion method. It avoids strings altogether and uses mathematical operations (modulo and division) to extract the digits of each number. This is generally faster and more memory-efficient.
**Time:** O(D * log(R)), where D is the number of integers in the range `[left, right]` and R is the value of `right`. The logic is the same as the previous approach, but arithmetic operations are generally faster than string conversions, leading to better practical performance. · **Space:** O(1) for auxiliary space, excluding the output list. This method only uses a few integer variables for its calculations, making it very memory-efficient. The output list can still take up to O(D) space.
**Pros:** More efficient in both time and space compared to the string conversion method.; Avoids the overhead of creating and garbage-collecting string objects.
**Cons:** The logic, while simple, might be slightly less direct for those more comfortable with string manipulation.
### Explanation
Similar to the first approach, we iterate through every number `num` from `left` to `right`. To check if `num` is self-dividing, we use a loop that processes the number's digits without converting it to a string. We use a temporary variable, say `currentNum`, initialized to `num`. In a `while` loop that continues as long as `currentNum > 0`, we extract the last digit using the modulo operator: `digit = currentNum % 10`. We then check the same two conditions:

1.  If `digit` is 0, the number is not self-dividing.
2.  If the original number `num` is not divisible by `digit`, it's not self-dividing.

If either check fails, we immediately know `num` is not self-dividing and can move to the next number in the range. After checking a digit, we remove it from `currentNum` by integer division: `currentNum = currentNum / 10`. If the `while` loop completes for all digits, the number is self-dividing and is added to the result list.

```java
import java.util.ArrayList;
import java.util.List;

class Solution {
    public List<Integer> selfDividingNumbers(int left, int right) {
        List<Integer> result = new ArrayList<>();
        for (int i = left; i <= right; i++) {
            if (isSelfDividing(i)) {
                result.add(i);
            }
        }
        return result;
    }

    private boolean isSelfDividing(int num) {
        int temp = num;
        while (temp > 0) {
            int digit = temp % 10;
            if (digit == 0) {
                return false; // Cannot contain digit 0
            }
            if (num % digit != 0) {
                return false; // Not divisible by one of its digits
            }
            temp /= 10;
        }
        return true;
    }
}
```
### Algorithm
- Initialize an empty list `ans`.
- Iterate through each number `i` from `left` to `right`.
- For each number `i`, check if it is a self-dividing number using a helper function.
- **Helper function `isSelfDividing(num)`:**
  - Create a temporary copy of the number, `temp = num`.
  - Loop as long as `temp > 0`.
  - Extract the last digit using the modulo operator: `digit = temp % 10`.
  - If `digit` is 0, return `false`.
  - If the original number `num` is not divisible by `digit` (i.e., `num % digit != 0`), return `false`.
  - Remove the last digit from `temp` by integer division: `temp /= 10`.
  - If the loop completes, return `true`.
- If the helper function returns `true` for `i`, add `i` to the `ans` list.
- Return the `ans` list.

# Solutions
### Java

```java
class Solution { public List < Integer > selfDividingNumbers ( int left , int right ) { List < Integer > ans = new ArrayList <>(); for ( int i = left ; i <= right ; ++ i ) { if ( check ( i )) { ans . add ( i ); } } return ans ; } private boolean check ( int num ) { for ( int t = num ; t != 0 ; t /= 10 ) { int x = t % 10 ; if ( x == 0 || num % x != 0 ) { return false ; } } return true ; } }
```

### CPP

```cpp
class Solution { public: vector < int > selfDividingNumbers ( int left , int right ) { vector < int > ans ; for ( int i = left ; i <= right ; ++ i ) if ( check ( i )) ans . push_back ( i ); return ans ; } bool check ( int num ) { for ( int t = num ; t ; t /= 10 ) { int x = t % 10 ; if ( x == 0 || num % x ) return false ; } return true ; } };
```

### Python

```python
class Solution : def selfDividingNumbers ( self , left : int , right : int ) -> List [ int ]: return [ num for num in range ( left , right + 1 ) if all ( i != '0' and num % int ( i ) == 0 for i in str ( num )) ]
```