首页　>　文章列表　>　最小的重复数字中的1的个数

最小的重复数字中的1的个数

数字个数最小重复
180 2023-09-03

在这个问题中，我们只需要打印最小单位中的 1 的数量。

reunit 是一个正数，如休闲数学中的 11、111 或 1111，只有数字 1。reunit 的形式为 $mathrm{(10*n-1)/9}$

示例

$mathrm{(10*10-1)/9}$ 给出 11。

$mathrm{(10*100-1)/9}$ 给出 111。

$mathrm{(10*1000-1)/9}$ 给出 1111。

上面的问题指出，我们给定任意正整数 N，其单位数字为 3，我们需要确定能被给定数字 N 整除的最小单位。

例如，

如果我们给出 N=13。

输出：6

N，即 13 完美整除 111111 得到 8547。

111111 是最小的重单位，可被 13 整除。因此，最小重单位中的 1 数量为 6，给出所需的输出。

算法

因为我们知道重复次数是 1、11、111、1111 等等。 x 之后的后续 reunit 可以定义为 $mathrm{(x*10+1)}$。

该算法仅基于这样的概念：如果整数 N 留下的余数为 rem，则重新单位余数将始终为 $mathrm{(rem*10+1)%N}$。

确定重新单位数可能会过于繁琐，因为该数字可能非常大，因此我们将通过更新余数直到其变为 0 并通过每一步更新来计算 1 的数量来找到答案。使余数为 0 所需的迭代次数将是最小重单位中 1 的数量。

下面是算法的逐步描述 -

第 1 步− 将变量剩余声明为 1，以存储每次 N 剩下的余数 iteration 和 itr 为 1 来计算迭代次数。
第 2 步 − 使用 while 循环，直到余数变为 0。
第 3 步 − 每一步，更新余数并增加 itr 1.
第 4 步 − 一旦余数等于 0，则返回 itr。< /p>

让我们对 N=13 尝试这种方法。

因为我们在 while 循环之前将剩余部分和 itr 声明为 1。

现在，

在第 1 次迭代中，余数将为 (余数*10+1)%N，即 11。余数=11且itr=2。按照同样的算法，直到余数变为0。
在迭代 2 时，余数=7 且 itr=3
在迭代 3 时，余数=6 且 itr=4
在迭代 4 时，余数=9 且 itr=5
在迭代 5 时，余数=0 且 itr=6。

由于余数变为 0，我们将返回 itr，即 6，这是所需的输出。

方法

下面是上述方法在 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;
}