Number of ones in the smallest repunit

Moderate

0/80

Average time to solve is 30m

Contributed by

0 upvote

Asked in companies

Problem statement

Given a positive integer ‘N’ whose unit digit is 3. Find the number of 1's in the smallest repunit, which is divisible by the given number N. Every number whose unit digit is 3 has a repunit as its multiple. A repunit is a number that has only 1. It is of the form (10 * N – 1)/9.

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

Input format :

The first line of input contains an integer T denoting the number of test cases.
The next line contains an integer 'N', whose unit’s digit is 3.

Output format :

For each test case, a number of 1s in the smallest repunit is divisible by the given number N.
The output of each test case will be printed in a separate line.

Note:

You don’t have to print anything; it has already been taken care of. Just implement the given function.

Constraints:

1 <= T <= 5
1 <= N <= 100000

 Where ‘T’ is the total number of test cases, and N is the number.

Sample Input 1 :

1
3

Sample Output 1 :

Explanation of the sample Input 1:

The number 111 is the first repunit which is divisible by 3.

Sample Input 2 :

1
13

Sample Output 2 :

Hint 1

Generalize the sequence.

Approaches (1)

Approach 1

Generalize the sequence.

The repunits are 1, 11, 111, 1111, …. and the next repunit to X will always be X * 10 + 1.
If the remainder left by repunit X is R, then the remainder left by the next repunit will always be (R * 10 + 1)% N. Since the repunit can be very large, there is no need to find the repunit number.
Simply counting the number of ones will give us the answer.
So, find out the remainders of all repunit numbers until the remainder becomes 0. Once it does, then the count of iterations done to make the remainder 0 will be the number of 1’s.

Time Complexity

O(N), where N denotes the given number.

We are looping remainder from 1 till it becomes perfectly divisible by N, therefore the final time complexity will be O(N).

Space Complexity

O(1)

Since we are not using any extra space.

(100% EXP penalty)

Number of ones in the smallest repunit

Console