在因子中查找尾随零

我需要找到给定数字的尾随零。在因子中查找尾随零

对于较小的输入，它可以很好地工作，但对于较长的输入，它不能很好地工作。

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

在因子中查找尾随零

回答

相关问题