What is the time complexity of Factorial Trailing Zeroes?

The optimal solution has a time complexity of O(log(n)).

What data structures are used to solve Factorial Trailing Zeroes?

This problem uses Math. Understanding these concepts is essential for solving this Medium problem efficiently.

What are the key insights for solving Factorial Trailing Zeroes?

Insight 1: Trailing zeroes in a factorial are produced by pairs of 2 and 5 in the prime factorization of the factorial. Since there are always more factors of 2 than factors of 5, the number of trailing zeroes is determined by the number of factors of 5. Insight 2: To find the number of factors of 5 in n!, we need to count how many multiples of 5, 25, 125, etc., are present in the numbers from 1 to n. A number like 25 contributes two factors of 5 (5*5), 125 contributes three factors of 5 (5*5*5), and so on.

Which companies ask LeetCode 172. Factorial Trailing Zeroes in interviews?

This problem is frequently asked at Google.

JavaScript is required for the full interactive experience. However, all content is accessible without JavaScript.

Factorial Trailing Zeroes - LeetCode 172 Solution

Q: How to solve Factorial Trailing Zeroes?

The solution counts the number of factors of 5 in the prime factorization of n!. This is done by iteratively dividing 'n' by 5 and adding the quotient to the count. In each iteration, we are essentially counting the multiples of 5, 25, 125, and so on, that are less than or equal to 'n'. The sum of these counts gives us the total number of factors of 5, which is equal to the number of trailing zeroes.

Factorial Trailing Zeroes - Complete Solution Guide

Factorial Trailing Zeroes is LeetCode problem 172, a Medium level challenge. This complete guide provides step-by-step explanations, multiple solution approaches, and optimized code in python3, java, cpp, c.

Problem Statement

Given an integer n , return the number of trailing zeroes in n! . Note that n! = n * (n - 1) * (n - 2) * ... * 3 * 2 * 1 . Example 1: Input: n = 3 Output: 0 Explanation: 3! = 6, no trailing zero. Example 2: Input: n = 5 Output: 1 Explanation: 5! = 120, one trailing zero. Example 3: Input: n = 0 Output: 0 Constraints: 0 <= n <= 10 4 Follow up: Could you write a solution that works in logarithmic time complexity?

Detailed Explanation

The problem asks us to find the number of trailing zeroes in the factorial of a given non-negative integer 'n'. A trailing zero is a zero digit at the end of a number's decimal representation. For example, 5! = 120 has one trailing zero, and 10! has two trailing zeroes. The input is a non-negative integer 'n' (0 <= n <= 10^4), and the output is the number of trailing zeroes in n!.

Solution Approach

The solution counts the number of factors of 5 in the prime factorization of n!. This is done by iteratively dividing 'n' by 5 and adding the quotient to the count. In each iteration, we are essentially counting the multiples of 5, 25, 125, and so on, that are less than or equal to 'n'. The sum of these counts gives us the total number of factors of 5, which is equal to the number of trailing zeroes.

Step-by-Step Algorithm

Step 1: Initialize a variable 'count' to 0. This variable will store the number of trailing zeroes.
Step 2: While 'n' is greater than 0, perform the following steps:
Step 3: Divide 'n' by 5 using integer division (n = n // 5 in Python or n /= 5 in other languages). This gives the number of multiples of 5 in the range [1, n].
Step 4: Add the result of the division to the 'count'.
Step 5: Repeat steps 3 and 4 until 'n' becomes 0.
Step 6: Return the 'count'.

Key Insights

Insight 1: Trailing zeroes in a factorial are produced by pairs of 2 and 5 in the prime factorization of the factorial. Since there are always more factors of 2 than factors of 5, the number of trailing zeroes is determined by the number of factors of 5.
Insight 2: To find the number of factors of 5 in n!, we need to count how many multiples of 5, 25, 125, etc., are present in the numbers from 1 to n. A number like 25 contributes two factors of 5 (5*5), 125 contributes three factors of 5 (5*5*5), and so on.
Insight 3: We can efficiently count the factors of 5 by repeatedly dividing 'n' by increasing powers of 5 (5, 25, 125, ...). We keep track of the sum of the integer quotients obtained at each division.

Complexity Analysis

Time Complexity: O(log(n))

Space Complexity: O(1)

Topics

This problem involves: Math.

Companies

Asked at: Google.

Factorial Trailing Zeroes | LeetCode 172

Medium

Math

Time: O(log(n))Space: O(1)

Solution Code

Available in:

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

View Full Solution on GitHubGitHub Solution View on LeetCodeLeetCode

Problem Info

Description

Problem 172: Factorial Trailing Zeroes - Detailed explanation and solution approaches.

Topics

Math

Companies

Google

Stats

Difficulty:Medium

Languages:4

Companies:1

Problem #:172

Problem Explanation

💡

Think Before You Code

🤔 Ask Yourself

→What is the input? What output do I need?
→Can I solve a smaller version of this problem first?
→What patterns have I seen in similar problems?

✏️ Try This First

Before looking at the solution, try to solve it on paper with a simple example!

🚀 Try on LeetCode

Solution Approach

📋

Step-by-Step Solution

6 steps

1
Step 1: Initialize a variable 'count' to 0. This variable will store the number of trailing zeroes.
2
Step 2: While 'n' is greater than 0, perform the following steps:
3
Step 3: Divide 'n' by 5 using integer division (n = n // 5 in Python or n /= 5 in other languages). This gives the number of multiples of 5 in the range [1, n].
4
Step 4: Add the result of the division to the 'count'.
5
Step 5: Repeat steps 3 and 4 until 'n' becomes 0.
6
Step 6: Return the 'count'.

💡

Pro Tip for Students

Try tracing through each step with a small example on paper before coding. Understanding "why" each step happens is more important than memorizing the code!

⚡

Complexity Analysis

⏱️

Time Complexity

O(log(n))

🚀 Logarithmic - Very efficient! Halves the problem each step.

💾

Space Complexity

O(1)

💪 Constant space - Uses same memory regardless of input!

📝

Why?

The time complexity is logarithmic because we are repeatedly dividing 'n' by 5. The number of iterations is proportional to the base-5 logarithm of 'n'. The space complexity is constant because we are only using a few variables to store the count and intermediate values, regardless of the size of 'n'.

📖New to Big O? Click to learn more

Big O Notation - Quick Guide

O(1)Best - Instant

O(log n)Excellent - Binary Search

O(n)Good - One loop

O(n log n)OK - Sorting

O(n²)Slow - Nested loops

O(2ⁿ)Very Slow - Recursion

Alternative Approaches

Iterative factorial calculation (naive approach)

Calculate the factorial of 'n' and then count the number of trailing zeroes by repeatedly dividing by 10 until the result is not divisible by 10. This is inefficient for large values of 'n'.

Time: O(n) for factorial calculation + O(k) for counting trailing zeros where k is the number of trailing zeros.Space: O(1)

Trade-offs: This approach is not feasible for even moderately sized 'n' because the factorial grows very rapidly and will lead to integer overflow. The provided solution using factors of 5 is significantly better.

✨

Key Insights

1Insight 1: Trailing zeroes in a factorial are produced by pairs of 2 and 5 in the prime factorization of the factorial. Since there are always more factors of 2 than factors of 5, the number of trailing zeroes is determined by the number of factors of 5.
2Insight 2: To find the number of factors of 5 in n!, we need to count how many multiples of 5, 25, 125, etc., are present in the numbers from 1 to n. A number like 25 contributes two factors of 5 (5*5), 125 contributes three factors of 5 (5*5*5), and so on.
3Insight 3: We can efficiently count the factors of 5 by repeatedly dividing 'n' by increasing powers of 5 (5, 25, 125, ...). We keep track of the sum of the integer quotients obtained at each division.

📚

Key Terms Explained

For Students

Edge Cases

Edge case 1: n = 0. The solution correctly returns 0, as 0! = 1, which has no trailing zeroes.
Edge case 2: n is a large number. The solution correctly handles large values of 'n' as long as the integer division operation doesn't overflow. The problem constraints limit n to 10^4, so integer overflow is not a concern here.

⚠️

Common Mistakes to Avoid

✗Common mistake 1: Directly calculating n! and then counting trailing zeros. This is very inefficient because the factorial grows extremely rapidly, leading to overflow issues and high computational cost.

✗Common mistake 2: Only considering multiples of 5 and forgetting to account for multiples of higher powers of 5 (25, 125, etc.). For instance, if n=25, you need to account for the fact that 25 contributes two factors of 5.

✅

Learning Tip

Every mistake is a learning opportunity! When you make an error, understand why it happened before moving on.

🌍

Where is This Used in Real Life?

💼Real-world scenario 1: Determining the accuracy of calculations involving factorials. For example, if you are calculating probabilities using factorials, knowing the number of trailing zeroes can give you a rough idea of the precision required to represent the result.

🏦Real-world scenario 2: Analyzing the efficiency of algorithms that involve factorials. Understanding the properties of factorials, like the number of trailing zeroes, allows for better resource management and optimization.

💡Understanding real-world applications helps you see the "why" behind algorithms. It's not just about passing interviews—these concepts power the apps and websites you use every day!

Author's Notes

💡 Key Insight

When dealing with arrays, always consider if sorting would simplify the problem. Many array problems have O(n) solutions using hash maps or two-pointer technique.

🎯 Interview Tip

If stuck, try working through a small example by hand. The pattern often reveals itself.

⚠️ Watch Out

Always test your solution with edge cases: empty input, single element, and boundary values.

Written by Saswata Mondal

Software Engineer • Algorithms Enthusiast • Interview Coach

👨‍💻

About the Author

👨‍💻

Saswata MondalAuthor400+ LC Problems

B.Tech CSE, IEM Kolkata | LeetCode Rating: 1672 (Top 15%)

Certified: IBM Java Developer, NPTEL Programming in Java

Last updated: November 20, 2024LeetCode Profile GitHub

This solution has been crafted based on my experience solving 400+ LeetCode problems. Each explanation is designed to help you understand the underlying concepts, not just memorize the code.

Community Tips & Insights

I was asked this exact problem at my Google interview. The interviewer wanted me to optimize space complexity.

@InterviewProJul 13

Try solving this without using extra space first. It's a great exercise for understanding the underlying pattern.

@CodeNinjaJul 6

❓

Frequently Asked Questions

What techniques are commonly tested in medium-difficulty problems?

Medium problems often require combining multiple techniques: two-pointer with hash maps, BFS/DFS with state tracking, dynamic programming with optimization, or divide-and-conquer approaches. They test your ability to recognize patterns and choose the right combination of techniques.

How should I practice algorithm problems effectively?

Focus on understanding patterns rather than memorizing solutions. After solving a problem, review optimal solutions and understand the intuition. Group similar problems to recognize patterns. Practice explaining your approach out loud. Review problems after a few days to test retention.

What is the optimal approach for "Factorial Trailing Zeroes"?

For this medium-level Math problem, the key is to identify the core pattern. Analyze the input constraints to determine acceptable time complexity. Consider whether standard techniques can optimize the solution. Always handle edge cases and validate your approach with examples before coding.

🤖 Need help with this problem?