Trailing Zeros

Trailing Zeros

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

Example

11! = 39916800, so the out should be 2

Challenge

O(log N) time

Solution: 只要找里面有多少个5, 乘出来就会有多少个0,因为2永远是够的

# of 5:n/5+n/25+n/(5^3)…..

public long trailingZeros(long n) {
    long base = 5;//important to use long type
    long count = 0;
    while (n >= base) {
        count += n / base;
        base *= 5;
    }
    return count;
}
FacebookTwitterGoogle+Share

Leave a Reply

Your email address will not be published. Required fields are marked *