172. Factorial Trailing Zeroes

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

Note: Your solution should be in logarithmic time complexity.

Solution:

Method 1: iterative

The idea is to count the number of  5¹, 5², 5³, ...



Code:

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

Method 2: recursive:



Code:

public class Solution {
    public int trailingZeroes(int n) {
        return n == 0 ? 0 : n / 5 + trailingZeroes(n / 5);
    }
}