Self Dividing Numbers

Difficulty: Easy | Acceptance: 80.80% | Paid: No Topics: Math

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 % 8 == 0, and 128 % 2 == 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].

• Examples
• Constraints
• Brute Force
• String Conversion

Examples

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 <= 10^4

Brute Force

Intuition Iterate through each number in the range. For each number, extract its digits using modulo and division operations to check if it is divisible by all its digits.

Steps

• Loop from left to right inclusive.
• For each number num, store it in a temporary variable temp.
• While temp is greater than 0, extract the last digit d = temp % 10.
• If d is 0 or num % d is not 0, the number is not self-dividing.
• Otherwise, divide temp by 10 to remove the last digit.
• If the loop completes successfully, add num to the result list.

class Solution:
    def selfDividingNumbers(self, left: int, right: int) -> list[int]:
        res = []
        for num in range(left, right + 1):
            temp = num
            is_self_dividing = True
            while temp > 0:
                digit = temp % 10
                if digit == 0 or num % digit != 0:
                    is_self_dividing = False
                    break
                temp //= 10
            if is_self_dividing:
                res.append(num)
        return res

Complexity

• Time: O(N * D) where N is the number of integers in the range and D is the average number of digits.
• Space: O(1) excluding the space required for the output list.
• Notes: This is the most efficient approach as it avoids string conversion overhead.

String Conversion

Intuition Convert the number to a string to easily iterate over each digit. This simplifies digit extraction but involves slight overhead for type conversion.

Steps

• Loop from left to right.
• Convert the current number num to a string s.
• If s contains the character ‘0’, skip this number.
• Iterate through each character in s, convert it back to an integer d.
• If num % d is not 0, the number is not self-dividing.
• If all digits pass the check, add num to the result list.

class Solution:
    def selfDividingNumbers(self, left: int, right: int) -> list[int]:
        res = []
        for num in range(left, right + 1):
            s = str(num)
            if '0' in s:
                continue
            is_valid = True
            for char in s:
                if num % int(char) != 0:
                    is_valid = False
                    break
            if is_valid:
                res.append(num)
        return res

Complexity

• Time: O(N * D) where N is the range size and D is the number of digits.
• Space: O(D) to store the string representation of the number.
• Notes: Slightly slower due to string allocation and conversion, but often more readable.