Solution Explanation: Factorial Trailing Zeroes

The problem asks to find the number of trailing zeros in the factorial of a given integer n (n!). A trailing zero is a zero at the end of a number. The number of trailing zeros is determined by the number of times 10 is a factor in n!. Since 10 = 2 * 5, and there will always be more factors of 2 than 5 in n!, the number of trailing zeros is solely determined by the number of factors of 5 in n!.

Approach: Counting Factors of 5

The solution uses a mathematical approach to efficiently count the number of factors of 5 in n!. Instead of calculating the factorial directly (which would be computationally expensive for large n), we iteratively divide n by 5 and accumulate the results.

1. Iteration: The code repeatedly divides n by 5. Each division represents the number of multiples of 5 within the range [1, n].
2. Accumulation: The result of each division is added to a running total (ans). This accounts for all multiples of 5, 25, 125, and so on. For example:
   • n/5 counts multiples of 5.
   • (n/5)/5 counts multiples of 25 (which contain two factors of 5).
   • ((n/5)/5)/5 counts multiples of 125 (which contain three factors of 5), and so on.
3. Termination: The loop continues until n becomes 0, meaning there are no more multiples of 5 to consider.

Time and Space Complexity

• Time Complexity: O(log5n). The number of iterations in the while loop is logarithmic because we repeatedly divide n by 5. The number of divisions required is proportional to the logarithm of n base 5.
• Space Complexity: O(1). The algorithm uses a constant amount of extra space regardless of the input size.

Code Implementation in Various Languages

The core logic remains the same across different programming languages. The only variations are syntax-specific details.

Python3

class Solution:
    def trailingZeroes(self, n: int) -> int:
        ans = 0
        while n:
            n //= 5
            ans += n
        return ans

Java

class Solution {
    public int trailingZeroes(int n) {
        int ans = 0;
        while (n > 0) {
            n /= 5;
            ans += n;
        }
        return ans;
    }
}

C++

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

Go

func trailingZeroes(n int) int {
	ans := 0
	for n > 0 {
		n /= 5
		ans += n
	}
	return ans
}

TypeScript

function trailingZeroes(n: number): number {
    let ans = 0;
    while (n > 0) {
        n = Math.floor(n / 5);
        ans += n;
    }
    return ans;
}

All these code snippets implement the same efficient algorithm to solve the problem, achieving logarithmic time complexity. They avoid the computationally expensive task of calculating the full factorial.