[LintCode] Trailing Zeros

java 4 2016-02-29 13:03
女装

Problem

Write an algorithm which computes the number of trailing zeros in n factorial.

Challenge

11! = 39916800, so the output should be 2

Note

i是5的倍数,先找有多少个5(1个0),然后找多少个25(2个0),补上,然后多少个125(3个0),补上……

Solution

class Solution {
    public long trailingZeros(long n) {
        long i = 5;
        long count = 0;
        while (i <= n) { 
        //n = 125, i = 5, count = 25; 25个5 
        //i = 25, count += 5(5个25)= 30; i = (1个)125, count  += 1 = 31; 
            count += n / i;
            i = i * 5;
        }
        return count;
    }
}
女装
文章评论