Q9. Ram is very good at mathematics. He was given a number n and was told to find out number of trailing zeroes in n! in logarithmic time. Can you help him?

Intuition Behind the Algorithm

The problem presented to Ram involves finding the number of trailing zeroes in the factorial of a given number n. This task hinges on understanding that trailing zeroes are formed by the product of 2 and 5. However, in factorials, the number of 2s is always more than or equal to the number of 5s. Thus, the problem simplifies to counting the number of 5s in the factorial's prime factorization.

#include <iostream>
using namespace std;

// Function to count the number of trailing zeros in n!
int factorial_trailing_zeros(int n) {
    int count_zeros = 0; // Initialize count of trailing zeros to 0

    // Loop to divide n by 5 and add the quotient to count_zeros
    while (n > 0) {
        n = n / 5;        // Divide n by 5
        count_zeros += n; // Add the quotient to count_zeros
    }

    return count_zeros; // Return the count of trailing zeros
}

int main() {
    int n;
    cin >> n; // Input the number n

    int ans = factorial_trailing_zeros(n); // Compute the number of trailing zeros
    cout << ans << endl; // Output the result

    return 0;
}

Code Walkthrough

The provided C++ code effectively addresses this problem. The function factorial_trailing_zeros takes an integer n and initializes count_zeros to zero. It then enters a while loop, which continues as long as n is greater than zero. Inside the loop, n is divided by 5, and this quotient is added to count_zeros. This division essentially counts how many times 5 is a factor in numbers from 1 to n. The loop iteratively divides n by 5 to account for additional factors of 5 in numbers like 25, 125, etc., where 5 appears more than once. Once the loop ends, count_zeros, representing the number of trailing zeroes in n!, is returned.

The main function reads an integer n and uses factorial_trailing_zeros to compute the answer, which is then outputted.

Time and Space Complexity Analysis

The time complexity of the algorithm is O(log5(n)). This is because the loop divides n by 5 in each iteration, effectively reducing the problem size logarithmically. The space complexity is O(1), as the algorithm uses a fixed amount of space regardless of the input size.

Key Points of the Algorithm

• Efficiency in Counting 5s: The algorithm smartly counts the number of times 5 is a factor in the factorial of n, which is the essence of finding trailing zeroes.

• Logarithmic Time Complexity: The approach ensures that the time complexity is logarithmic, making it efficient for large values of n.

• Simplicity and Elegance: The implementation is straightforward and easy to understand, yet powerful in its computation.

Conclusion

The provided solution is optimal for the given problem. It elegantly solves the problem in logarithmic time, which is a significant improvement over naive methods that might attempt to compute the factorial directly.