Last Updated: 20 Apr, 2021
Smallest number divisible by K
Moderate
Asked in company
Ninja’s favorite numbers are the numbers whose all digits are ‘1’. So Let's consider numbers that have only the digit ‘1’. For example, [ ‘1’, ‘11’, ‘111’ … ]
You are given an integer ‘K’, Your task is to find the number of digits in the Ninja’s smallest favorite number that is divisible by ‘K’. If there is no such number that is divisible by ‘K’, then return -1.
Input Format:
The first line contains an integer 'T' which denotes the number of test cases or queries to be run.
The first line of each test case contains an integer denoting the value of ‘K’.
Output Format:
For each test case, print a single line containing a single integer denoting the number of digits in the smallest number that is divisible by given ‘K’ if it exists else print ‘-1’.
The output of each test case will be printed in a separate line.
Note:
You do not need to input or print anything, and it has already been taken care of. Just implement the given function.
Constraints:
1 <= T <= 5
1 <= K <= 10 ^ 5
Where ‘T’ is the total number of test cases, and ‘K’ is the given integer.
Time limit: 1 sec.
Approaches
We will loop through each number starting from ‘1’ and check its remainder when divided by ‘K’, if we get 0 then we return the number of digits in the current number, and we will stop the loop when we get a reminder twice i.e a cycle is found. For this, we can use a visited array of size ‘K’.
In this Approach we cannot directly increase the number by adding ‘1’ in digits and checking if it is divisible by ‘K’ or not as this may lead to integer overflow after some limit, So instead of checking the module with the original number we will check module with number modulo ‘K’ as for any ‘X’, ‘X’ % ‘K’ is same as ( ‘X’ % ‘K’ ) % ‘K’.
Algorithm:
- Declare a variable ‘currentNumber’ and initialize it by 1.
- Declare a variable say ‘len’ to store the length of the current number.
- Declare an array say ‘visited’ of size ‘K’ and initialize all elements with 0.
- Run an infinite loop.
- If ‘currNumber’ % ‘K’ == 0
- Return ‘len’
- If ‘visited[currNumber’ % K]’ is true, break the loop.
- Set ‘visited[currNumber’ % K]’ to true.
- Update ‘currNumber’ to next number by adding 1 in its digits and then take module with ‘K’ i.e. ‘currNumber’ = (‘currNumber’*10 + 1 ) % ‘K’.
- Increase ‘len’ by 1.
- If ‘currNumber’ % ‘K’ == 0
- Return -1 as no valid number is found
Here we can observe that if ‘K’ is even then we cannot find any number, as all numbers will end at ‘1’. Also if ‘K’ is a multiple of 5, then there exists no number such that it is divisible by ‘K’, as again the number should end with either 5 or 0 in order to divide by 5.
In all other cases, we can prove that one solution will exist. Consider any ‘K’ that is not multiple of 5 and 2. Consider all numbers from length 1 up to length ‘K’ i.e [ ‘1’, ‘11’, ‘111’, … ‘111...K times’ ]. Now we say that no two number given the same remainder when divided by ‘K’, then it becomes obvious that one of these ‘K’ numbers will definitely give 0 when divided by ‘K’, as at most there can ‘K’ reminders i.e. 0 to ‘K - 1’, so from pigeonhole principle we can say that one of there must be divisible by ‘K’.
We can prove by contradiction that [ ‘1’, ‘11’, ‘111’, … ‘111… ’K’ times ] will give unique reminders when divided by ‘K’ such that ‘K’ is not multiple of 2 and 5. Consider any two numbers that give the same remainder when divided by ‘K’ say ‘X’ and ‘Y’, ‘X’ > ‘Y’. Now ‘X’ - ‘Y’ should be divisible by ‘K’ but notice that ‘X’ - ‘Y’ will have a format like 111...000 i.e. ‘X’ - ‘Y’ will end at 0, and for ‘X’ - ‘Y’ to be divisible by ‘K’, ‘K’ must be multiple of 10 (5 and 2). But in our case, ‘K’ is neither multiple of 2 nor 5. So we can say that no two numbers from the above list will give the same remainder when divided by ‘K’.
Algorithm:
- Declare a variable ‘currentNumber’ and initialize it by 1.
- Declare a variable say ‘len’ to store the length of the current number.
- Run a loop from ‘i’ = 1 to ‘K’
- If ‘currNumber’ % ‘K’ == 0
- Return ‘len’
- Update ‘currNumber’ to next number by adding 1 in its digits and then take module with ‘K’ i.e. ‘currNumber’ = (‘currNumber’*10 + 1 ) % ‘K’.
- Increase ‘len’ by 1.
- If ‘currNumber’ % ‘K’ == 0
- Return -1 as no valid number is found.