LeetCode (Math) Factorial Trailing Zeroes

2018-07-09

Factorial Trailing Zeroes

Given an integer n, return the number of trailing zeroes in n!.

Example 1:

1
2
3

Input: 3
Output: 0
Explanation: 3! = 6, no trailing zero.

Example 2:

1
2
3

Input: 5
Output: 1
Explanation: 5! = 120, one trailing zero.

Note: Your solution should be in logarithmic time complexity.

思路：就是求给定的数n的阶乘中末尾0的个数，首先能想到的最简单的算法是求出这个阶乘值，然后从末尾开始统计0的个数当做结果返回即可。这里需要注意的是int型的溢出问题，如果使用int来计算阶乘的话，在计算13！的时候就溢出，所以这里我们采用了BigInteger来计算。

代码如下：

package irisqp.leetcode;

import java.math.BigInteger;

public class TrailingZeroes {
    public int trailingZeroes(int n) {
        int res = 0;
        BigInteger temp = BigInteger.valueOf(1);

        for (int i = n; i > 0; i--) {
            temp = temp.multiply(BigInteger.valueOf(i));
        }
        System.out.println(temp);
        String s = String.valueOf(temp);

        int j = s.length()-1;
        while (j >= 0 && s.charAt(j) == '0') {
            res++;
            j--;
        }

        return res;
    }
    public static void main(String[] args) {

        TrailingZeroes tz = new TrailingZeroes();

        System.out.println(tz.trailingZeroes(4860));
    }
}

　　最后提交时超时了，暗示我们还应该有更简单的做法。

　　通过观察我们可以发现：从1到4的阶乘末尾都没有0，而从5开始，所有的阶乘末尾都会有0。因为5！=120, 这个数开始，以后每个数的阶乘都是它的倍数，比如6！=120*6=720，然后我们会发现7,8,9的阶乘末尾都只有1个零，直到10的阶乘为362800,末尾是两个0，然后我们发现15的阶乘末尾有3个0，20的阶乘末尾有4个0，而25的阶乘末尾有6个0。

　　我们发现只要是5的倍数，末尾就可以至少有n/5个0。至于为什么25的阶乘末尾有6个0，是因为25/5=5，除下来的值还大于5，而当这个5/5=1时，才是我们的结果5+1=6。

java代码如下：

  /**
     * 5的阶乘为120，以后只有在乘以5的倍数时候才会增加0，比如10的阶乘后面有2个0
     * 5 10 15 20 25 对应的末尾为0的个数是 1 2 3 4 6。为什么25是6呢，因为25/5以后得5，还有1个5，所以是5+1，总共有6个0.
     * @param n
     * @return
     */
    public int trailingZeroes2(int n) {
        int res = 0;
        if (n < 5) {
            return res;
        }

        while (n >= 5) {
                n /= 5;
                res += n;
        }

        return res;
    }
    public static void main(String[] args) {

        TrailingZeroes tz = new TrailingZeroes();

        System.out.println(tz.trailingZeroes2(91));
    }
}