Question

link

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

Note: Your solution should be in logarithmic time complexity.

Credits:
Special thanks to @ts for adding this problem and creating all test cases.

            <div id="tags" class="btn btn-xs btn-warning">Show Tags</div>
            <span class="hide">

              <a class="btn btn-xs btn-primary" href="/tag/math/">Math</a>

            </span>

        </div>

Analysis

This question I’ve seen it quite a few time, also. We’re basically count the number of factor 5s.

Eg.

n = 5, count = 1

n = 6, count = 1

n = 10, count = 2

n = 24, count = 4

n = 25, count = 6

n = 26, count = 6

Solution

Please read this post [[LintCode] Trailing Zeros of Factorial].

Code

public class Solution {
    public int trailingZeroes(int n) {
        if (n < 5) {
            return 0;
        }
        int res = 0;
        long base = 5;
        while (n >= base) {
            res += n / base;
            base *= 5;
        }
        return res;
    }
}

another pretty good solution:

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