【LeetCode】Factorial Trailing Zeroes解題レポート

【LeetCode】Factorial Trailing Zeroes解題レポート
[LeetCode]
https://leetcode.com/problems/factorial-trailing-zeroes/
Total Accepted: 58324 Total Submissions: 177641 Difficulty: Easy
Question
Given an integer n, return the number of trailing zeroes in n!.
Note: Your solution should be in logarithmic time complexity.
Ways
この問題は一見暴力的に解くことができない.
分析してみると、n!いくつかの5組成があります.含まれる2と5からなるpairの個数を計算すればよい.5の個数は2より少ないので,2と5からなるpairの個数は5の個数で決まる.15を観察!=5(その中の5,10,15から)が3つあるので、n/5を計算すればいいです.でも25!=6個の5(その中の5,10,15,20,25から5個あり、もう1個の5は25=(5*5)からのもう1つの5)からあるので、n/5を計算するだけでなく、n/5/5,n/5/5,n/5/5,...,n/5/5,,/5は商が0になるまで計算します.
アルゴリズムではこのcount+=n/i;何個あるかを直接見るという意味です.例えばn=26;では、26/5=5です.26/25=1;だから結果は5+1=6個です.
方法は比較的巧みで,どうせ私は考えられなかった.
また注意して、必ずlong、intを使うと結果が間違っていて、私は何をしているのか分からない顔をしています.

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

AC:1ms
Date
2016年05月8日