Leetcode – Self Dividing Numbers Solution in Python

Spread the love

In this extensive article, we will delve into the ‘Self Dividing Numbers’ problem from Leetcode. This problem is a great representation of number manipulation and is frequently encountered in coding interviews.

Before we commence on the journey to solve this problem, let’s take a look at what it is asking us to do.

Problem Statement

The problem statement from Leetcode is as follows:

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

Example:

Input: left = 1, right = 22

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

Approach 1: Brute Force Solution

A simple solution to this problem would be to iterate through all the numbers in the given range, and for each number, check if it is self-dividing. We can convert the number to a string and iterate through each character in the string. If the digit is zero or if the number is not divisible by the digit, we know it’s not a self-dividing number.

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

        return [n for n in range(left, right+1) if isSelfDividing(n)]

In this solution, the time complexity is O(D), where D is the total number of digits in the range [left, right].

Approach 2: Optimized Solution

The brute force approach works, but it is not the most efficient solution. An optimized solution could avoid checking the numbers that have the digit ‘0’ because they cannot be self-dividing.

This can be done by incrementing the number by 1 if the current number or the next number has a digit of ‘0’. Otherwise, increment the number by 10 if the last digit is ‘0’.

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

        result = []
        while left <= right:
            if '0' in str(left):
                left += 1
                continue
            if isSelfDividing(left):
                result.append(left)
            left += 1
        return result

This optimized solution helps to avoid unnecessary checking and reduce the number of iterations in the algorithm. The time complexity remains O(D), but the actual number of iterations is reduced.

Conclusion

In this comprehensive guide, we dissected the ‘Self Dividing Numbers’ problem from Leetcode. We examined two approaches to solve the problem, starting with a brute-force solution, then moving on to an optimized solution that minimizes the number of iterations.

Leave a Reply