最小的重複數字中的1的個數-C++-PHP中文網

最小的重複數字中的1的個數

PHPz

發布： 2023-09-06 17:21:09

轉載

1253 人瀏覽過

最小的重複數字中的1的個數

在這個問題中，我們只需要列印最小單位中的 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。 p>
第 3 步 − 每一步，更新餘數並增加 itr 1.
第 4 步 − 一旦餘數等於 0，則回傳 itr。

讓我們對 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;
}

登入後複製