Jobs

Interviews

Discussions

Self Dividing Numbers

Easy

Asked by:

55 views

Topics:

Arrays

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] (both inclusive).

Example 1:

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

Example 2:

Input: left = 47, right = 85
Output: [48,55,66,77]

Constraints:

1 <= left <= right <= 10⁴

Try coding it in LeetCode

Self Dividing Numbers

Easy

Asked by:

55 views

Topics:

Arrays

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] (both inclusive).

Example 1:

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

Example 2:

Input: left = 47, right = 85
Output: [48,55,66,77]

Constraints:

1 <= left <= right <= 10⁴

Try coding it in LeetCode

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

What is the range of numbers for the left and right boundaries? Specifically, what are the maximum and minimum possible values?
If `left` is greater than `right`, should I return an empty list or is that considered an invalid input?
Are the left and right boundaries inclusive or exclusive?
Are there any specific performance expectations or memory constraints I should be aware of, given the range of numbers?
Should I return the self-dividing numbers in any specific order (e.g., ascending)?

Brute Force Solution

Approach

The brute force strategy involves examining every number within a given range to determine if it's self-dividing. For each number, we will check if every digit divides the number evenly.

Here's how the algorithm would work step-by-step:

Take the starting number and the ending number of the range we're given.
Consider each number one by one between the start and end numbers.
For each number, break it down into its individual digits.
Check if each digit divides the original number evenly. If any digit is zero, or if any digit doesn't divide the number evenly, then it's not self-dividing.
If all digits divide the original number evenly and there are no zero digits, then the number is self-dividing. Keep track of the self-dividing numbers.
Continue this process until you've checked every number in the range.
In the end, provide the list of all self-dividing numbers that you identified.

Code Implementation

def self_dividing_numbers(left_number, right_number):
    self_dividing_number_list = []

    for number_to_check in range(left_number, right_number + 1):
        is_self_dividing = True
        number_string = str(number_to_check)

        for digit_character in number_string:
            digit = int(digit_character)

            # Exclude numbers with 0 as a digit as division by 0 is not allowed
            if digit == 0:
                is_self_dividing = False

                break

            # If the number is not divisible by the digit, it's not self dividing
            if number_to_check % digit != 0:
                is_self_dividing = False

                break

        # We only append if all digits divided the number
        if is_self_dividing:
            self_dividing_number_list.append(number_to_check)

    return self_dividing_number_list

Big(O) Analysis

Time Complexity

O(n*d) – The algorithm iterates through a range of numbers from the start to the end, where n is the size of the range (end - start + 1). For each number in the range, we extract its digits to check if it's self-dividing. Let d represent the maximum number of digits any number in the range can have. For each of the n numbers, we perform up to d divisions to determine if it's self-dividing. Therefore, the time complexity is proportional to the product of the range size (n) and the maximum number of digits in a number within that range (d), leading to O(n*d).

Space Complexity

O(N) – The algorithm stores self-dividing numbers in a list. In the worst-case scenario, every number within the range [left, right] is a self-dividing number. Thus, the list grows proportionally to the size of the range, which can be denoted as N, where N is the number of integers in the given range (right - left + 1). Therefore, the auxiliary space is O(N).

Optimal Solution

Approach

The goal is to find numbers where each digit divides the number evenly. The best way to do this is to check each number digit by digit, skipping numbers that have a zero as a digit because zero can never be a divisor.

Here's how the algorithm would work step-by-step:

For each number in the given range, examine each digit.
If a digit is zero, that number cannot be self-dividing so we skip checking the number altogether.
For a number to be self-dividing, each digit has to divide the number with no remainder.
If every digit divides the number evenly, we know we have found a self-dividing number and add it to our results.
Return the list of all the self-dividing numbers we found in the range.

Code Implementation

def self_dividing_numbers(left, right):
    result = []

    for number in range(left, right + 1):
        number_string = str(number)
        is_self_dividing = True

        for digit_char in number_string:
            digit = int(digit_char)

            # Numbers with zero cannot be self-dividing
            if digit == 0:
                is_self_dividing = False
                break

            # Check if the number is divisible by the digit
            if number % digit != 0:
                is_self_dividing = False
                break

        # If it is self dividing, then add to result
        if is_self_dividing:
            result.append(number)

    return result

Big(O) Analysis

Time Complexity

O(n*d) – The outer loop iterates through numbers in the range [left, right], where n represents the number of integers in this range (right - left + 1). For each number, we iterate through its digits to check if it is self-dividing. The number of digits, d, in each number is limited by the number of digits in the upper bound (right). In the worst case, we iterate through all digits of each number in the range. Therefore, the time complexity is proportional to the number of integers times the number of digits for each integer, which approximates to O(n*d). Since d is related to the number of digits in right, we can consider this more precisely as n times the number of digits in the largest number in the range.

Space Complexity

O(N) – The primary space usage comes from storing the self-dividing numbers in a result list. In the worst-case scenario, every number in the input range is self-dividing. Therefore, if the range contains N numbers, the result list could potentially store all N numbers. This leads to an auxiliary space complexity that is linearly proportional to the size of the input range.

Edge Cases

Case	How to Handle
Left boundary greater than right boundary	Return an empty list if left > right as it represents an invalid range.
Input range contains 0	Numbers containing 0 are not self-dividing, so the solution must skip them during the self-dividing check.
Single digit numbers	Single-digit numbers should be included if they are self-dividing (i.e., 1-9).
Numbers with repeated digits, e.g., 11, 22, 33	The self-dividing check must correctly handle repeated digits when performing the modulo operation.
Large input range (e.g., 1 to 10000)	The solution should iterate efficiently through the range to avoid exceeding time limits.
Numbers that are divisible by their digits but the digits are not unique	The self-dividing check needs to handle repeating digits, for example, 122, which is divisible by 1 and 2.
The range only contains a single number	The code should check if the single number is self dividing and return a list containing that number or an empty list.
Integer overflow when number is very large	Since the input is an integer range, overflow isn't likely, but should be considered by limiting the maximum input number.

Left boundary greater than right boundary

How to Handle:

Return an empty list if left > right as it represents an invalid range.

Input range contains 0

How to Handle:

Numbers containing 0 are not self-dividing, so the solution must skip them during the self-dividing check.

Single digit numbers

How to Handle:

Single-digit numbers should be included if they are self-dividing (i.e., 1-9).

Numbers with repeated digits, e.g., 11, 22, 33

How to Handle:

The self-dividing check must correctly handle repeated digits when performing the modulo operation.

Large input range (e.g., 1 to 10000)

How to Handle:

The solution should iterate efficiently through the range to avoid exceeding time limits.

Numbers that are divisible by their digits but the digits are not unique

How to Handle:

The self-dividing check needs to handle repeating digits, for example, 122, which is divisible by 1 and 2.

The range only contains a single number

How to Handle:

The code should check if the single number is self dividing and return a list containing that number or an empty list.

Integer overflow when number is very large

How to Handle:

Since the input is an integer range, overflow isn't likely, but should be considered by limiting the maximum input number.

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

What is the range of numbers for the left and right boundaries? Specifically, what are the maximum and minimum possible values?
If `left` is greater than `right`, should I return an empty list or is that considered an invalid input?
Are the left and right boundaries inclusive or exclusive?
Are there any specific performance expectations or memory constraints I should be aware of, given the range of numbers?
Should I return the self-dividing numbers in any specific order (e.g., ascending)?

Brute Force Solution

Approach

The brute force strategy involves examining every number within a given range to determine if it's self-dividing. For each number, we will check if every digit divides the number evenly.

Here's how the algorithm would work step-by-step:

Take the starting number and the ending number of the range we're given.
Consider each number one by one between the start and end numbers.
For each number, break it down into its individual digits.
Check if each digit divides the original number evenly. If any digit is zero, or if any digit doesn't divide the number evenly, then it's not self-dividing.
If all digits divide the original number evenly and there are no zero digits, then the number is self-dividing. Keep track of the self-dividing numbers.
Continue this process until you've checked every number in the range.
In the end, provide the list of all self-dividing numbers that you identified.

Code Implementation

def self_dividing_numbers(left_number, right_number):
    self_dividing_number_list = []

    for number_to_check in range(left_number, right_number + 1):
        is_self_dividing = True
        number_string = str(number_to_check)

        for digit_character in number_string:
            digit = int(digit_character)

            # Exclude numbers with 0 as a digit as division by 0 is not allowed
            if digit == 0:
                is_self_dividing = False

                break

            # If the number is not divisible by the digit, it's not self dividing
            if number_to_check % digit != 0:
                is_self_dividing = False

                break

        # We only append if all digits divided the number
        if is_self_dividing:
            self_dividing_number_list.append(number_to_check)

    return self_dividing_number_list

Big(O) Analysis

Time Complexity

Space Complexity

Optimal Solution

Approach

Here's how the algorithm would work step-by-step:

For each number in the given range, examine each digit.
If a digit is zero, that number cannot be self-dividing so we skip checking the number altogether.
For a number to be self-dividing, each digit has to divide the number with no remainder.
If every digit divides the number evenly, we know we have found a self-dividing number and add it to our results.
Return the list of all the self-dividing numbers we found in the range.

Code Implementation

def self_dividing_numbers(left, right):
    result = []

    for number in range(left, right + 1):
        number_string = str(number)
        is_self_dividing = True

        for digit_char in number_string:
            digit = int(digit_char)

            # Numbers with zero cannot be self-dividing
            if digit == 0:
                is_self_dividing = False
                break

            # Check if the number is divisible by the digit
            if number % digit != 0:
                is_self_dividing = False
                break

        # If it is self dividing, then add to result
        if is_self_dividing:
            result.append(number)

    return result

Big(O) Analysis

Time Complexity

Space Complexity

Edge Cases

Case	How to Handle
Left boundary greater than right boundary	Return an empty list if left > right as it represents an invalid range.
Input range contains 0	Numbers containing 0 are not self-dividing, so the solution must skip them during the self-dividing check.
Single digit numbers	Single-digit numbers should be included if they are self-dividing (i.e., 1-9).
Numbers with repeated digits, e.g., 11, 22, 33	The self-dividing check must correctly handle repeated digits when performing the modulo operation.
Large input range (e.g., 1 to 10000)	The solution should iterate efficiently through the range to avoid exceeding time limits.
Numbers that are divisible by their digits but the digits are not unique	The self-dividing check needs to handle repeating digits, for example, 122, which is divisible by 1 and 2.
The range only contains a single number	The code should check if the single number is self dividing and return a list containing that number or an empty list.
Integer overflow when number is very large	Since the input is an integer range, overflow isn't likely, but should be considered by limiting the maximum input number.

Left boundary greater than right boundary

How to Handle:

Return an empty list if left > right as it represents an invalid range.

Input range contains 0

How to Handle:

Numbers containing 0 are not self-dividing, so the solution must skip them during the self-dividing check.

Single digit numbers

How to Handle:

Single-digit numbers should be included if they are self-dividing (i.e., 1-9).

Numbers with repeated digits, e.g., 11, 22, 33

How to Handle:

The self-dividing check must correctly handle repeated digits when performing the modulo operation.

Large input range (e.g., 1 to 10000)

How to Handle:

The solution should iterate efficiently through the range to avoid exceeding time limits.

Numbers that are divisible by their digits but the digits are not unique

How to Handle:

The self-dividing check needs to handle repeating digits, for example, 122, which is divisible by 1 and 2.

The range only contains a single number

How to Handle:

The code should check if the single number is self dividing and return a list containing that number or an empty list.

Integer overflow when number is very large

How to Handle:

Since the input is an integer range, overflow isn't likely, but should be considered by limiting the maximum input number.