Solution Explanation: Self Dividing Numbers

The problem asks to find all self-dividing numbers within a given range [left, right]. A self-dividing number is divisible by every digit it contains, and it cannot contain the digit zero.

Approach:

The solution employs a straightforward approach:

1. check(x) function: This helper function efficiently determines if a number x is self-dividing. It iterates through the digits of x by repeatedly dividing by 10. For each digit, it checks two conditions:

   • If the digit is 0, x is not self-dividing (returns false).
   • If x is not divisible by the digit, x is not self-dividing (returns false).
   • If all digits pass these checks, the function returns true.

2. Main loop: The main part iterates through the numbers from left to right. For each number, it calls the check(x) function. If check(x) returns true, the number is added to the result list.

3. Return: Finally, the list of self-dividing numbers is returned.

Time and Space Complexity Analysis:

• Time Complexity: The time complexity is dominated by the nested loops. The outer loop iterates right - left + 1 times. The inner loop (check function) iterates at most log10(right) times (number of digits in the largest number). Therefore, the overall time complexity is approximately O((right - left) * log10(right)). This simplifies to O(n log n) where n is the range size.

• Space Complexity: The space complexity is determined by the size of the result list. In the worst case, all numbers in the range could be self-dividing. Thus, the space complexity is O(right - left), which simplifies to O(n) where n is the range size.

Code Implementations:

The provided code demonstrates the solution in multiple programming languages: Python, Java, C++, Go, TypeScript, and Rust. All implementations follow the same logic, differing only in syntax and language-specific features. The check function is consistently implemented for efficiency. The main loop iterates through the range and uses the check function to filter self-dividing numbers.

Example (Python):

class Solution:
    def selfDividingNumbers(self, left: int, right: int) -> List[int]:
        def check(x: int) -> bool:
            y = x
            while y:
                if y % 10 == 0 or x % (y % 10):
                    return False
                y //= 10
            return True
 
        return [x for x in range(left, right + 1) if check(x)]

The other language implementations are structurally very similar, making use of the helper function check to efficiently identify self-dividing numbers within the specified range.