Self Dividing Numbers

Easy
0/40
Average time to solve is 15m
profile
Contributed by
27 upvotes
Asked in company
SAP Labs

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.
Detailed explanation ( Input/output format, Notes, Images )
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
Sample Input 1:
2
10 30
15 45
Sample output 1:
11 12 15 22 24
15 22 24 33 36 44
Explanation For Sample Input 1:
Test Case 1:

For the first test case, the output [11, 12, 15, 22, 24] is the required list of self-dividing numbers containing only those numbers that have all the digits that can divide the number and do not contain the digit ‘0’ in it.

Test Case 2:

For the first test case, The output [15, 22, 24, 33, 36, 44] is the required list of self-dividing numbers containing only those set of numbers that have all the digits which can divide the number and that do not contain the digit ‘0’ in it.
Sample Input 2:
2
1 22
100 150
Sample output 2:
1 2 3 4 5 6 7 8 9 11 12 15 22
111 112 115 122 124 126 128 132 135 144
Hint

Try for each number in the given range, to directly test if that number is self-dividing.

Approaches (1)
Self Dividing Numbers

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.
Time Complexity

O(D * log(UPPER)), where D is the number of integers in the range [LOWER, UPPER].

 

Since we are iterating over all the elements given in the range [LOWER, UPPER] therefore, depending on the number of integers present ‘D’ in the range, and also on the number of digits which would be checked for every integer which would be the worst-case of the number of digits present in the UPPER that is given i.e. log(UPPER) 

 

So the complexity here grows by O(D * log(UPPER)).

Space Complexity

O(D), where ‘D’ is the number of integers in the range [ LOWER, UPPER].

 

Since, in the worst case, all the numbers in the range [LOWER, UPPER] can be answered.

Code Solution
(100% EXP penalty)
Self Dividing Numbers
Full screen
Console