Smallest number divisible by K

Moderate
0/80
Average time to solve is 30m
40 upvotes
Asked in company
LinkedIn

Problem statement

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.

Detailed explanation ( Input/output format, Notes, Images )

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.

Sample Input 1:

2
1
8

Sample Output 1:

1
-1

Explanation of Sample Input 1:

Test case 1:
‘1’ is itself divided by one, that has only 1 digit, hence the answer will be 1.

Test case 2:
There is no number whose all digits are ‘1’ and divisible 8 , so the answer will be -1.

Sample Input 2:

1
11

Sample Output 2:

2

Explanation of Sample Input 2:

Test case 1:
‘11’ is itself divided by 11 which have 2 digits hence the answer will be 2.
Hint

Use properties of arithmetic modulo.

Approaches (2)
Arithmetic Modulo

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.
  • Return -1 as no valid number is found
Time Complexity

O(K), where ‘K’ is the given value.

 

As at most, there can be K reminders i.e 0 to K -1 so we are running a loop at most ‘K’ times that takes O(K) time. Hence the overall time complexity is O(K).

Space Complexity

O(K), where ‘K’ is the given value.

 

As we are using an array to keep track of visited remainders,  that takes O(K) space.

Code Solution
(100% EXP penalty)
Smallest number divisible by K
Full screen
Console