The smallest number of 1's in a repeated number

In this problem, we only need to print the number of 1's in the smallest unit.

reunit is a positive number, like 11, 111, or 1111 in casual math, with only the number 1. The form of reunit is $\mathrm{(10*n-1)/9}$

Example

$\mathrm{(10*10-1)/9}$ gives 11.

$\mathrm{(10*100-1)/9}$ gives 111.

$\mathrm{(10*1000-1)/9}$ gives 1111.

The above question points out that we are given any positive integer N, whose unit number is 3, and we need to determine the smallest unit that can be divisible by the given number N.

For example,

If we give N=13.

Output: 6

N, that is, 111111 is a perfect divisor of 13 to get 8547.

111111 is the smallest unit of weight divisible by 13. Therefore, the number of 1's in the smallest weight unit is 6, giving the desired output.

algorithm

Because we know that the number of repetitions is 1, 11, 111, 1111 and so on. The subsequent reunit after x can be defined as $\mathrm{(x*10 1)}$.

This algorithm is based solely on the concept that if an integer N leaves a remainder rem, the reunit remainder will always be $\mathrm{(rem*10 1)\%N}$.

Determining the number of reunits might be too tedious as the number can be very large, so we will find the answer by updating the remainder until it becomes 0 and counting the number of 1's with each update step. The number of iterations required to get the remainder to 0 will be the number of 1's in the smallest weight unit.

The following is a step-by-step description of the algorithm -

• Step 1− Declare the variable remainder as 1 to store the remainder of each N iteration and itr are 1 to count the number of iterations.

• Step 2 − Use a while loop until the remainder becomes 0. p>

• Step 3 − Every step, update the remainder and increase itr 1.

• Step 4 − Once the remainder is equal to 0, return itr.

Let's try this approach on N=13.

Because we declare the remainder and itr as 1 before the while loop.

Now,

• In the 1st iteration, the remainder will be (remainder*10 1)%N, which is 11. Remainder=11 and itr=2. Follow the same algorithm until the remainder becomes 0.

• At iteration 2, remainder=7 and itr=3

• At iteration 3, remainder=6 and itr=4

• At iteration 4, remainder=9 and itr=5

• At iteration 5, remainder=0 and itr=6.

Since the remainder becomes 0, we will return itr, which is 6, which is the desired output.

method

The following is the implementation of the above method in C -

#include <iostream>
#include<bits/stdc++.h>

using namespace std;

//function to calculate no of ones in smallest repunit
int numberOfones(int N){  
   int remainder=1;
   
   int itr=1; // to store no of iterations
   
   while(remainder!=0){
      //update remainder
      remainder=(remainder*10 + 1)% N;
   
      itr++; //increase itr by 1 to get number of 1's in repunit
   }
   
   return itr;
}
int main(){
   int N=23;
   cout<<numberOfones(N);
   return 0;
}

Output

22

The smallest number of repeating units divisible by 23 will consist of 22 ones.

in conclusion

In the above article, we tried to solve the problem of finding the number of smallest units that can be divisible by any positive integer N with a single digit of 3. I hope this article can help you clarify the concept of this issue.

The above is the detailed content of The smallest number of 1's in a repeated number. For more information, please follow other related articles on the PHP Chinese website!