在因子中查找尾隨零

我需要找到給定數字的尾隨零。在因子中查找尾隨零

對於較小的輸入，它可以很好地工作，但對於較長的輸入，它不能很好地工作。

long input=s.nextInt(); 
    long mul=1; 
    int count=0; 
      while(input!=1 && input<1000000000) 
      { 
       log.debug("mul="+mul+"Input="+input+"count="+count); 
       mul =mul*input; 
       input--; 
       while(mul%10==0) 
       { 
        count++; 
        mul=mul/10; 
       } 
       mul=mul%100; 
       //if() 
      } 
      System.out.println(count); 
      log.debug(count); 
      count=0;

對於輸入

6//Working Correct 
3//Working Correct 
60//Working Correct 
100//Working Correct 
1024//Working Correct 

23456//Working Wrong 
8735373//Working Wrong

預期輸出：

0 
14 
24 
253 
5861//My output is 5858 
2183837//My output is 2182992

來源

2016-02-25 Renigunda

你試過尋找這個問題嗎？已經討論了很多次 – radoh

是否被定義爲長？ –

@GilbertLeBlanc是的，其長 – Renigunda

首先，我非常喜歡提問者和回答者提供的解決方案。但是這並不能回答你的代碼出了什麼問題。

我花了一段時間才弄明白，但我認爲你所做的一個非常微妙的數學假設實際上並不成立。你的假設是你可以在每次迭代中減少模100，並且不會丟失任何東西。這個假設結果是錯誤的。

減量模100在某些情況下不起作用。 100 = 5^2 * 2^2。問題在於你正在失去5s和2s，這可能最終導致更多的0，這意味着你的程序提供的答案可能比真正的答案要少。例如，如果在某次迭代中結果爲125，那麼在您減少模數100後，您將得到25.如果在下一次迭代時乘以72等數值，則結果將是（25 * 72） = 1800，意味着2個零。現在回頭看看如果你乘以125乘以72將會得到什麼結果：（125 * 72）= 9000。這是3個零。所以你的程序錯過了第三個零，因爲減去模100將125 = 5^3變成25 = 5^2（即失去了5的倍數）。

如果你不遵循數學論證，你可以做什麼來證明我是正確的：將你的mod降低100，mod降低1000.我敢打賭它接近正確的答案。只要你注意溢出，你甚至可以嘗試10000來更近一些。

但最終，這種解決方案的方法是有缺陷的，因爲你的模減少將失去5s和2s的倍數足夠高的數字。結論：使用提問者和回答者的方法，但要確保你能證明它的工作原理！（他已經爲你繪製了證明！）

來源

2016-02-25 21:46:41 TheGreatContini

在這樣的情況下，我有多個0的我可以使用while（mul％10 == 0） { count ++; mul = mul/10; } – Renigunda

@Renigunda不，我不認爲你明白。請在程序中嘗試用mod 1000替換mod 100，我向你保證，它會返回比以前更高的答案。然後重新閱讀我的回覆。 – TheGreatContini

我瞭解你的概念。無論如何，我可以解決問題，而不會導致溢出錯誤？ – Renigunda

-1

而不是實際計算的答案，這將花費的時間太長了，可能溢出的整數，只是檢查數量在數字5。

這是可行的，因爲尾隨零的數量由5的數量決定。在一個階乘數中，總是有2個因子比5個因子多。數字中5個因子的數目是尾隨零的數量。

int answer = 0; 
for (int i = 5; i <= input; i+=5) { //i starts at 5 because we do not count 0 
    answer++; 
}

來源

2016-02-25 21:16:37

可愛的解決方案，但他的代碼有什麼問題？ – TheGreatContini

尾隨零數= 5s數+ 25s數+125s數+5 ...數/ 5 – Shooter

@問題者和回答者如果是這種情況，那麼我們需要相應地找到2，4，8和10 。是這樣嗎？ – Renigunda

你失去零由於您的號碼被截斷國防部100 125將增加3個零。 625增加了4. 3125增加了5. 但是，在調零後你只保留2位數。（它適用於100和1024一致）。

然而，當25或更大的5次冪進來時，由於100位數的截斷，8可能會成爲倍數2，所以可能會丟失幾個零。

而不是做一個mul = mul％100，你應該保留更多的數字，這取決於數字本身。

多少？相同的最高功率5比數字少。

來源

2016-02-25 21:45:34 Shooter

是的，我同時發佈了類似的答案。好的趕上！ – TheGreatContini

在因子中查找尾隨零

回答

相關問題