Last Updated: 22 Feb, 2021

Number of ones in the smallest repunit

Moderate

Asked in companies

Solve now

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.

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.

Solve now

Approaches

01 Approach

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.

Solve now