algoadvance

Leetcode 172. Factorial Trailing Zeroes

Problem Statement

172. Factorial Trailing Zeroes

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

Note: Your solution should be in logarithmic time complexity.

Clarifying Questions

1. Q: What is the range of the input n? A: The input n is a non-negative integer which can be as large as up to (10^9).

2. Q: Do we need to actually compute the factorial of n? A: No, we only need to count the number of trailing zeroes in n!.

3. Q: What constitutes a “trailing zero”? A: Trailing zeros are the number of consecutive 0 digits at the end of the number.

Strategy

Key Insight

A trailing zero is produced by a factor of 10 in the number. Since 10 is the product of 2 and 5, each pair of these factors in the factorial contributes to a trailing zero. In any factorial, there are more factors of 2 than factors of 5, so the number of trailing zeros is determined by the number of factors of 5.

Steps to Solve

1. Count factors of 5:
   • First, count how many multiples of 5 are there in numbers from 1 to n.
   • Second, count how many multiples of (5^2 = 25) are there, as each of these contributes an extra factor of 5.
   • Continue this process for (5^3), (5^4), etc., until (5^k) where (5^k > n).

Code Implementation

public class Solution {
    public int trailingZeroes(int n) {
        int count = 0;
        while (n >= 5) {
            n /= 5;  // Integer division to count multiples of 5, 25, 125, etc.
            count += n;
        }
        return count;
    }
}

Time Complexity

• Time Complexity: O(log5(n))
  • This is because the number of iterations needed is proportional to the number of times you can divide n by 5 before it becomes less than 5.
• Space Complexity: O(1)
  • The space requirement is constant, as only a couple of integer variables are used regardless of the input size.

This solution efficiently counts the number of trailing zeros in n! without having to compute the factorial itself, making it suitable for very large values of n as required.

Cut your prep time in half and DOMINATE your interview with AlgoAdvance AI

• Got blindsided by a question you didn’t expect?

• Spend too much time studying?

• Or simply don’t have the time to go over all 3000 questions?