algoadvance

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.
• Also, a self-dividing number does not contain any 0 digits.

Given a lower and upper number bound, output a list of every possible self-dividing number, including the bounds if possible.

You can assume that the input boundaries are always valid.

Clarifying Questions

1. Range Inclusion: Should the range include the lower and upper bounds?
   • Yes, include the lower and upper bounds.
2. Zero Handling: How to handle numbers with zero in their digits?
   • Numbers containing any zero digit are not self-dividing numbers.
3. Output Order: Should the output list be in any specific order?
   • The output list should be in ascending order since we will be iterating through the range in increasing order.

Strategy

1. Helper Function: Create a helper function is_self_dividing to check if a number is self-dividing.
   • Convert the number to its digit representation.
   • If any digit is 0 or the number is not divisible by any of its digits, return False.
   • Otherwise, return True.
2. Iterate Range: Iterate through the given range (inclusive) and collect all numbers that satisfy the self-dividing property using the helper function.
3. Collect Results: Return the list of self-dividing numbers.

Code

Here is the Python code to solve the problem:

def is_self_dividing(number):
    original = number
    while number > 0:
        digit = number % 10
        if digit == 0 or original % digit != 0:
            return False
        number //= 10
    return True

def selfDividingNumbers(left, right):
    result = []
    for num in range(left, right + 1):
        if is_self_dividing(num):
            result.append(num)
    return result

# Test the function
left = 1
right = 22
print(selfDividingNumbers(left, right))

Time Complexity

• Helper Function: For each number, the is_self_dividing function checks each digit, resulting in O(d) where d is the number of digits.
• Overall Iteration: The selfDividingNumbers function iterates through all numbers in the range [left, right], calling the helper function.
  • Let n be the count of numbers in the range, and assuming the average number of digits is log10(right), the overall time complexity becomes O(n * log10(right)).

In summary:

• Creating a helper function to check the self-dividing condition.
• Iterating through the range and gathering all self-dividing numbers.
• Complexity is O(n * log10(right)) which is efficient for typical input ranges allowed in common problems.

Try our interview co-pilot at AlgoAdvance.com

• Got blindsided by a question you didn’t expect?

• Spend too much time studying?

• Or simply don’t have the time to go over all 3000 questions?