Self Dividing Numbers

In order to solve this problem, we will go through each number in the range from left to right and check if that number is a self-dividing number. A number is self-dividing if it is divisible by each of its digits. We can find the digits of a number by converting it to a string.

Here is the Python code for the solution:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29

class Solution:
    def selfDividingNumbers(self, left: int, right: int) -> List[int]:
        # Initialize the list for the result
        result = []

        # Iterate through the range
        for num in range(left, right + 1):
            # Convert the current number to a string to be able to iterate over its digits
            str_num = str(num)

            # Initialize a flag for checking if the current number is self-dividing
            is_self_dividing = True

            # Check if the current number contains the digit 0
            if '0' in str_num:
                continue

            # Iterate over the digits of the current number
            for digit in str_num:
                # If the current number is not divisible by the current digit, it is not self-dividing
                if num % int(digit) != 0:
                    is_self_dividing = False
                    break

            # If the current number is self-dividing, add it to the result list
            if is_self_dividing:
                result.append(num)

        return result

In this solution, we first initialize the result list. Then we iterate through the range of numbers from left to right. We convert each number to a string to be able to iterate over its digits.

For each number, we initialize a flag is_self_dividing to True. We will set this flag to False if we find that the number is not self-dividing.

Next, we check if the number contains the digit 0. If it does, we continue to the next number because a self-dividing number is not allowed to contain the digit zero.

Then, we iterate over the digits of the number. If the number is not divisible by any of its digits, it is not self-dividing, so we set is_self_dividing to False and break the loop.

Finally, if is_self_dividing is still True after checking all the digits, the number is self-dividing, so we add it to the result list. When we have checked all the numbers in the range, we return the result list.

Identifying Problem Isomorphism

The problem “Self Dividing Numbers” can be approximately mapped to “Happy Number”.

In the “Self Dividing Numbers” problem, the task is to identify numbers within a range that have the property of being divisible by each of their digits.

In the “Happy Number” problem, you have to determine if a given number eventually reaches 1 when repeatedly replacing the number with the sum of the squares of its digits.

While these problems are not exactly isomorphic, both require operations on the digits of the numbers and a subsequent check for a certain condition (self-dividing or reaching 1). Both problems also involve some form of iteration or recursion to repeatedly perform operations until a certain condition is met.

“Self Dividing Numbers” is a simpler problem, as it involves a straightforward operation on each digit. On the other hand, “Happy Number” adds complexity by involving repeated operations until a certain state is reached.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16

class Solution:
	def selfDividingNumbers(self, left: int, right: int) -> List[int]:
		result = []

		for i in range(left, right+ 1):
			if "0" in str(i): continue
			val = i
			while val > 0:
				n = val % 10
				if i % n != 0:
					val = -1
				val = val // 10

			if val != -1: result.append(i)

		return result

Problem Classification

This problem falls under the category of mathematical computation and number theory with a touch of brute-force search. It is essentially about performing mathematical computations based on the digits of the number.

Here are the key ‘What’ components:

  1. Self-dividing numbers: These are numbers that are divisible by every digit they contain. They can’t contain the digit zero.
  2. Range: A specified range from ’left’ to ‘right’ within which the function needs to find self-dividing numbers.
  3. List of self-dividing numbers: The function needs to return a list of all the self-dividing numbers in the range.

This problem can be further classified as an enumeration problem, as it requires enumerating all numbers in a given range and checking if they meet a certain condition (being self-dividing). The enumeration involves both iterating over the range of numbers and iterating over each digit in a given number.

Language Agnostic Coding Drills

  1. Dissecting the Code:

This piece of code encapsulates several distinct concepts:

  • Concept 1: Basic iteration: The for loop iterates over the given range of integers from left to right.
  • Concept 2: List manipulation: An empty list ‘result’ is defined, to which elements (i.e., self-dividing numbers) are added.
  • Concept 3: String conversion and membership testing: Each number in the range is converted to a string to check if it contains a “0”.
  • Concept 4: Integer Division and Modulo Operations: These are used to iterate over and extract individual digits of a number.
  • Concept 5: Conditional Checks: Multiple conditions are checked within the for loop and the while loop - whether a number contains a 0, whether it’s divisible by its digits, etc.
  • Concept 6: Control flow: The continue statement is used to skip iterations, and a flag value (val = -1) is used to signal that a number isn’t self-dividing.
  1. Increasing order of Difficulty and Concept Descriptions:
  • Basic iteration (Level: Easy): This is a fundamental concept in most programming languages, enabling us to traverse through a set of elements.
  • List manipulation (Level: Easy): Another foundational concept in Python, we use lists to store and manage multiple data elements.
  • String conversion and membership testing (Level: Medium): The code converts integers to strings, enabling an easy way to check if a digit (0 in this case) exists in a number.
  • Conditional Checks (Level: Medium): Conditional checks are crucial for controlling the flow of the program based on certain conditions.
  • Integer Division and Modulo Operations (Level: Medium): These mathematical operations are used to extract individual digits from a number.
  • Control flow (Level: Hard): This concept, including understanding of how ‘continue’ works and how a flag value can be used to control flow, requires a deeper understanding of programming logic.
  1. Problem-solving Approach and Steps:

The approach here is to iterate over the given range of numbers and check each one to see if it’s a self-dividing number.

  • Step 1: Implement a loop to iterate over the range of numbers.
  • Step 2: Within this loop, first convert the number to a string and check if it contains “0”. If it does, continue to the next iteration.
  • Step 3: For numbers without a “0”, iterate over their digits by using integer division and modulo operations.
  • Step 4: Within this inner loop, check if the number is divisible by its current digit. If not, set a flag value to signal this and break the loop.
  • Step 5: After the inner loop, check the flag value. If it hasn’t been set (i.e., the number is self-dividing), add the number to the result list.
  • Step 6: After all iterations are done, the result list will contain all self-dividing numbers in the range.

Targeted Drills in Python

  1. Python Coding Drills for each Concept:

    • Concept 1: Basic Iteration

      1
2

      for i in range(5):
    print(i)

    • Concept 2: List Manipulation

      1
2
3
4

      list_items = []
list_items.append(1)
list_items.append(2)
print(list_items)

    • Concept 3: String conversion and Membership Testing

      1
2
3
4
5

      number = 1230
if "0" in str(number):
    print("Number contains 0.")
else:
    print("Number does not contain 0.")

    • Concept 4: Integer Division and Modulo Operations

      1
2
3
4
5

      number = 123
while number > 0:
    digit = number % 10
    print("Current digit:", digit)
    number = number // 10

    • Concept 5: Conditional Checks

      1
2
3
4
5

      number = 5
if number % 2 == 0:
    print("Even number.")
else:
    print("Odd number.")

    • Concept 6: Control flow

      1
2
3
4

      for i in range(10):
    if i % 2 == 0:
        continue
    print(i)

  2. Problem-Specific Concepts:

  • Checking for self-dividing numbers is a unique concept to this problem. We can encapsulate it in a function like so:

    1
2
3
4
5
6
7
8

    def is_self_dividing(number):
    temp = number
    while temp > 0:
        digit = temp % 10
        if number % digit != 0:
            return False
        temp = temp // 10
    return True
  1. Integration of these drills to solve the problem:

Start by initializing an empty result list. Then, iterate over the range of numbers from left to right. In each iteration, first convert the number to a string and check if it contains a “0” using the string conversion and membership testing drill. If it does, continue to the next iteration.

Otherwise, check if the number is a self-dividing number using the is_self_dividing function. If it is, add it to the result list using the list manipulation drill.

At the end of all iterations, the result list will contain all self-dividing numbers in the range. Here’s how all the pieces fit together:

1
2
3
4
5
6
7
8

def selfDividingNumbers(left, right):
    result = []
    for i in range(left, right + 1):
        if "0" in str(i):
            continue
        if is_self_dividing(i):
            result.append(i)
    return result