algoadvance

Leetcode 172. Factorial Trailing Zeroes

Problem Statement

You are given an integer n, and you need to return the number of trailing zeroes in n! (n factorial).

Clarifying Questions

1. What are trailing zeroes?
   • Trailing zeroes are the number of zeroes at the end of a number. For example, the number 100 has two trailing zeroes.
2. How do trailing zeroes in a factorial appear?
   • Trailing zeroes in a factorial appear due to the factors of 10 in the number. Since 10 is the product of 2 and 5, we need to count the number of 2s and 5s in the factors of n!. Generally, there are more factors of 2 than 5, so we only need to count the number of times 5 is a factor in the numbers from 1 to n.

Strategy

1. Count factors of 5:
   • For every number k in the range 1 to n, count how many times 5 is a factor in k.
   • Finally, sum these counts to get the number of trailing zeroes.
2. Efficiency:
   • Instead of checking each number’s prime factors, we can use:
     • floor(n / 5) to count multiples of 5
     • floor(n / 25) to count multiples of 25 (since every 25 contributes an additional factor of 5)
     • Continue this pattern with floor(n / 5^i) until 5^i > n

Time Complexity

• The algorithm primarily involves a series of divisions which run in logarithmic time with respect to n, so its time complexity is O(log n).

Code

#include <iostream>

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

int main() {
    Solution solution;
    int n = 100;  // Example input
    std::cout << "The number of trailing zeroes in " << n << "! is: " << solution.trailingZeroes(n) << std::endl;
    return 0;
}

Explanation

• We initialize count to 0.
• In a while loop, we repeatedly divide n by 5, adding the result to count.
• This loop continues as long as n is greater than or equal to 5.
• Finally, we return the count, which gives the total number of trailing zeroes in n!.

In this solution, we efficiently count the number of factors of 5 in the factorial, leading to the calculation of trailing zeroes.

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?