LeetCode 175 - Factorial Trailing Zeroes

Related:
LeetCode 175 - Factorial Trailing Zeroes
LeetCode 793 - Preimage Size of Factorial Zeroes Function
[LeetCode] Factorial Trailing Zeroes
Given an integer n, return the number of trailing zeroes in n!.
Note: Your solution should be in logarithmic time complexity.
那么这道题目就转化成为计算从1到n之间所有数的5的约数个数总和。很简单的想到能不能用n/5得到。比如当n为19的时候，19/5 = 3.8，那么就是有3个约数包含5的数，分别是5, 10, 15。但是有的数可能被5整除多次，比如说25。这样的数一个就能给最后的factorial贡献好几个5。
最后的解法就是对n/5+n/25+n/125+…+进行求和，当n小于分母的时候，停止。分母依次为5^1, 5^2, 5^2… 这样的话在计算5^2的时候，能被25整除的数里面的两个5，其中一个已经在5^1中计算过了。所以5^2直接加到count上。

    public int trailingZeroes(int n) {
        if ( n<0 ) return -1;
        int count = 0;
        for (int i=5; n/i>=1; i*=5) {
            count += n / i;
        }        
        return count;
    }

int trailingZeroes(int n) {

  int f5 = 0;

  for (; n / 5 > 0; n /= 5)

    f5 += n / 5;

  return f5;

}

https://www.cnblogs.com/yrbbest/p/4491644.html

题目可以转化为，求n!中含有多少个5。如何计算一个数里面有多少个5呢？我们可以用以下公式:

count = n / 5 + n / 25 + n / 125 + ....

就是用n除5来取得一开始的基数，当遇到5的倍数的时候，我们也要作相应的增加， 转换为循环的话我们可以先计算单个5的个数  n / 5，然后 n /= 5来计算 25的个数，然后再继续。最后返回count.

https://zxi.mytechroad.com/blog/math/leetcode-172-factorial-trailing-zeroes/

All trailing zeros are come from even_num x 5, we have more even_num than 5, so only count factor 5.

4! = 1x2x3x4 = 24, we haven’t encountered any 5 yet, so we don’t have any trailing zero.

5! = 1x2x3x4x5 = 120, we have one trailing zero. either 2×5, or 4×5 can contribute to that zero.

9! = 362880, we only encountered 5 once, so 1 trailing zero as expected.

10! = 3628800, 2 trailing zeros, since we have two numbers that have factor 5, one is 5 and the other is 10 (2×5)

What about 100! then?

100/5 = 20, we have 20 numbers have factor 5: 5, 10, 15, 20, 25, …, 95, 100.

Is the number of trailing zero 20? No, it’s 24, why?

Within that 20 numbers, we have 4 of them: 25 (5×5), 50 (2x5x5), 75 (3x5x5), 100 (4x5x5) that have an extra factor of 5.

So, for a given number n, we are looking how many numbers <=n have factor 5, 5×5, 5x5x5, …

Summing those numbers up we got the answer.

e.g. 1000! has 249 trailing zeros:

1000/5 = 200

1000/25 = 40

1000/125 = 8

1000/625 = 1

200 + 40 + 8 + 1 = 249

alternatively, we can do the following

1000/5 = 200

200/5 = 40

40/5 = 8

8/5 = 1

1/5 = 0

200 + 40 + 8 + 1 + 0 = 249

Time complexity: O(log5(n))

Space complexity: O(log5(n))

https://hellosmallworld123.wordpress.com/2014/05/23/write-an-algorithm-which-computes-the-number-of-trailing-zeros-in-n-factorial/
Not efficient code:

public static int zeroFactorial(int num) {

    int count = 0;

    for (int i = 1; i <= num; i++) {

        //count number of 5 in each element

        int element = i;

        while(element > 0 && element % 5 == 0) {

            element /= 5;

            count++;

        }

    }

    return count;

}

http://www.cnblogs.com/EdwardLiu/p/4207498.html
http://www.programcreek.com/2014/04/leetcode-factorial-trailing-zeroes-java/
最开始我的写法是：

 2 int findTrailingZeros(int  n)
 3 {
 4     // Initialize result
 5     int count = 0;
 6  
 7     // Keep dividing n by powers of 5 and update count
 8     for (int i=5; n/i>=1; i *= 5)
 9           count += n/i;
10  
11     return count;
12 }

在oj上提交会发现n =  1808548329时出错了，期望答案是452137076，实际答案是452137080

原因就是 i*5一直连乘时出现i = 5^14时，内存溢出(5^13 = 1220703125 < 2^31, but 5^14 = 6103515625 > 2^32)

Integer overflow之后会wrap around, 即Integer.MAX_VALUE + 1会成为Integer.MIN_VALUE, 详见Why Integer overflows wrap around

6103515625 wrap around之后 为正的1808548329-1 = 1808548328

原因是6103515625 % 2^32 = 1808548329 < 2 ^31，即 i 比32位Integer（共2^32）多出1808548329个数， 为 1808548328，又可以再进一次for 循环（本不应该进的）。所以答案偏大

解决办法：用除法代替乘法，用n / 5代替 i * 5，防止overflow，如最上面那段code所示

https://leetcode.com/discuss/19855/my-one-line-solutions-in-3-languages
O(log_5(N)) solution

    return n == 0 ? 0 : n / 5 + trailingZeroes(n / 5);

public int trailingZeroes(int n) { int cnt = 0; while(n>0){ cnt += n/5; n/=5; } return cnt; }
https://leetcode.com/discuss/20691/my-explanation-of-the-log-n-solution
// not reuse the multiplication
public int trailingZeroes(int n) { int power = 1; int c = 0; int f = (int) (n/(Math.pow(5, power))); while(f > 0){ c += f; f = (int) (n/(Math.pow(5, ++power))); } return c; }
https://leetcode.com/discuss/27261/2-lines-java-solution-any-better-code
int trailingZeroes(int n) { return (n < 5 ? 0 : (n/5 + trailingZeroes(n/5))); }
public int trailingZeroes(int n) { if(n < 5) return 0; else return n/5 + trailingZeroes(n/5); }
http://pages.cs.wisc.edu/~willb/cs302/spring-07/why-integer-overflow-cl.pdf
Related: Finding First Non-Zero Digit of N Factorial