#728

Easy

auto_awesomeMath-driven solution strategy

LeetCode Problem Workspace

Self Dividing Numbers

Identify self-dividing numbers in a given range by verifying divisibility against their digits.

Problem Statement

A self-dividing number is one that is divisible by every digit it contains. Importantly, self-dividing numbers cannot include the digit zero. For instance, 128 is a self-dividing number because it is divisible by 1, 2, and 8, but 101 is not because it contains zero.

Given two integers, left and right, the task is to return all self-dividing numbers in the inclusive range [left, right]. A number is self-dividing if each of its digits divides it evenly. The problem must be solved efficiently for ranges up to 10,000.

Examples

Example 1

Input: left = 1, right = 22

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

Example details omitted.

Example 2

Input: left = 47, right = 85

Output: [48,55,66,77]

Example details omitted.

Constraints

1 <= left <= right <= 104

Solution Approach

Iterate and Check Divisibility

Start by iterating through each number in the range [left, right]. For each number, convert it into a string or character array and check if it is divisible by each of its digits. Skip numbers containing the digit zero.

Avoid Zero Digits

Ensure that the number doesn't contain the digit zero, as self-dividing numbers cannot have zero digits. This check can be done by verifying the digits before performing divisibility tests.

Efficient Check for Divisibility

After verifying that the number doesn't contain zero, check if each digit divides the number without a remainder. If all digits divide the number, consider it a self-dividing number.

Complexity Analysis

Metric	Value
Time	We iterate through each digit in the given number; therefore, the time complexity is
Space	O(1)

The time complexity is O(n * m), where n is the length of the range and m is the number of digits in the number. For each number, we check divisibility by its digits. The space complexity is O(1) as we only need a few variables for the operation.

What Interviewers Usually Probe

Focus on how efficiently the candidate can iterate through a range and check divisibility.
Look for an understanding of string manipulation or array handling to extract digits from numbers.
Evaluate how the candidate handles edge cases such as numbers with zeros or single-digit numbers.

Common Pitfalls or Variants

Common pitfalls

Forgetting to check for the digit zero in the number, which would lead to incorrect results.
Inefficient implementation, causing slower performance for larger ranges.
Not handling numbers that have a single digit or edge cases like 10, 100, etc.

Follow-up variants

Consider a variant where the range can be negative, requiring handling of negative numbers.
Expand the problem to allow for ranges with floating-point numbers and non-integer divisibility.
Solve the problem without converting numbers to strings, relying purely on mathematical operations to extract digits.

FAQ

What is a self-dividing number?

A self-dividing number is a number that is divisible by each of its digits, and it cannot contain the digit zero.

How do I determine if a number is self-dividing?

Convert the number to a string or character array, then check if each digit divides the number evenly, while ensuring no digit is zero.

What is the time complexity of this problem?

The time complexity is O(n * m), where n is the length of the range and m is the number of digits in the number.

Can the solution handle large ranges?

Yes, the solution can handle large ranges up to 10,000 efficiently, depending on the implementation of the divisibility check.

What if the range contains negative numbers?

The problem as stated doesn't account for negative numbers, but a variant could be developed to handle them, potentially ignoring the negative sign.

terminal

Solution

Solution 1: Simulation

We define a function $\textit{check}(x)$ to determine whether $x$ is a self-dividing number. The implementation idea of the function is as follows:

1

2

3

4

5

6

7

8

9

10

11

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

Continue Practicing

#738 monotone increasing digits #710 random pick with blacklist #754 reach a number