Last Updated: 14 Apr, 2021

Self Dividing Numbers

Easy

Asked in company

Solve now

Problem statement

A Ninja wants to collect all possible self-dividing numbers from a given range of numbers.

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.

Given a ‘LOWER’ and ‘UPPER’ number bound, your task is to find all possible self-diving numbers in the range of ‘LOWER’ to ‘UPPER’.

Note:

A self-dividing number is not allowed to contain the digit zero.

You do not need to print anything; it has already been taken care of. Just implement the given function.

Example:

‘LOWER' = 1’  and, ‘UPPER' = 22’.

Output: [ 1, 2, 3, 4, 5, 6, 7, 8, 9, 11, 12, 15, 22 ]. Since all the numbers obtained in the output in the range of 'LOWER' to 'UPPER' are self-dividing numbers.

Input Format

The first line of input contains a single integer ‘T’ denoting the number of test cases given. Then next ‘T’ lines follow:

The first line of each test case input contains two single space-separated integers ‘LOWER’ and ‘UPPER’.

Output Format:

For every test case, return a list/array of every possible self dividing number, including the bounds (means ‘LOWER’ and ‘UPPER’ both are inclusive).

Constraint :

1 <= ‘T’ <= 10
1 <= ‘LOWER’ <= ‘UPPER’ <= 1000

‘T’ is the number of test cases given for the problem with ‘LOWER’ being the lower bound from where we start looking for the self-dividing integers until we reach ‘UPPER’, which is the upper bound. 

Time Limit: 1 sec

Solve now

Approaches

01 Approach

We want to test whether each digit is non-zero and divides the number.

For example, with number 128, we want to test d != 0 && 128 % d == 0 for d = 1, 2, 8. To do that, we need to iterate over each digit of the number.

A straightforward approach to the problem would be to convert the number into a character array (string in Python) and then convert it back to an integer to perform the modulo operation when checking N % d == 0.

We could also continually divide the number by 10 and peek at the last digit.

The algorithm to calculate the required self-dividing numbers will be:-

Start by iterating over the given range of numbers given i.e. between [LOWER, UPPER].
Break the iteration if the number has the digit zero in it and don't perform the check for that number i.e. whether it is to be added or not.
Now for each number test whether each digit divides the number and add it to our list (array) of required numbers if it does.
The digit wise divisibility can be easily checked by either:
- Converting the number into a character array (string in Python), and then convert back to an integer to perform the modulo operation when checking N % d == 0. Or,
- Keep continually dividing the number by 10 and peek at the last digit.
Once we have iterated for all the range of numbers given we finally return the obtained list of self-dividing numbers that we have gotten.

Solve now