# Factorial Trailing Zeroes **Difficulty:** MEDIUM [External](https://leetcode.com/problems/factorial-trailing-zeroes) Canonical: https://scaleengineer.com/dsa/problems/factorial-trailing-zeroes **Patterns:** [Math](https://scaleengineer.com/dsa/patterns/math) **Companies:** [Google](https://scaleengineer.com/companies/google) --- ## Problem 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 <= 104` **Follow up:** Could you write a solution that works in logarithmic time complexity? # Approaches ## Brute Force: Calculate Factorial This approach involves first calculating the exact value of `n!` and then counting the number of trailing zeroes. Since `n!` grows incredibly fast, standard integer types like `int` or `long` will overflow even for small values of `n`. Therefore, a special class capable of handling arbitrarily large integers, such as `BigInteger` in Java, is required. **Time:** O(n^2 * (log n)^2) · **Space:** O(n log n) **Pros:** Conceptually simple and easy to understand. **Cons:** Impractical due to massive time and space requirements.; Will result in "Time Limit Exceeded" for the given constraints.; Prone to overflow if not using a `BigInteger`-like structure. ### Explanation The most straightforward way to solve the problem is to simulate the process directly. First, we compute the value of `n!`. Then, we count how many times we can divide the result by 10 until it's no longer divisible. This count gives us the number of trailing zeroes. ```java import java.math.BigInteger; class Solution { public int trailingZeroes(int n) { if (n < 0) { return 0; // Factorial is not defined for negative numbers } // Step 1: Calculate n! BigInteger factorial = BigInteger.ONE; for (int i = 2; i <= n; i++) { factorial = factorial.multiply(BigInteger.valueOf(i)); } // Step 2: Count trailing zeroes int zeroCount = 0; BigInteger ten = BigInteger.TEN; while (factorial.compareTo(BigInteger.ZERO) > 0 && factorial.mod(ten).equals(BigInteger.ZERO)) { zeroCount++; factorial = factorial.divide(ten); } return zeroCount; } } ``` This method is correct but extremely inefficient. The value of `n!` becomes enormous very quickly, and operations on `BigInteger` are computationally expensive. For the given constraint `n <= 10^4`, this approach is not feasible. ### Algorithm - Handle the base case: if `n` is 0, `0!` is 1, which has 0 trailing zeroes. - Initialize a `BigInteger` variable, `factorial`, to `BigInteger.ONE`. - Iterate from 1 to `n`. In each iteration, multiply `factorial` by the current number `i` (converted to a `BigInteger`). - After computing the full factorial, initialize a counter `zeroCount` to 0. - Repeatedly check if the `factorial` is divisible by 10. As long as it is, increment `zeroCount` and divide `factorial` by 10. - The final `zeroCount` is the answer. ## Iterative Factor Counting A better approach is to realize that trailing zeroes are formed by factors of 10, which are pairs of 2 and 5. Since factors of 2 are always more abundant than factors of 5 in a factorial's prime factorization, the number of trailing zeroes is determined solely by the number of factors of 5. This approach iterates through all numbers from 1 to `n` and counts the total number of factors of 5. **Time:** O(n log n) · **Space:** O(1) **Pros:** Avoids calculating the large factorial value, thus preventing overflow.; Much more efficient than the brute-force approach. **Cons:** Not the most optimal solution.; The time complexity can be improved further. ### Explanation Instead of computing the massive `n!` value, we can analyze its prime factors. A trailing zero is created by a factor of 10, which is a product of 2 and 5. In the prime factorization of `n!`, the number of factors of 2 will always be greater than the number of factors of 5. Therefore, the number of trailing zeroes is limited by the count of factors of 5. We can iterate from 1 to `n` and for each number, count how many factors of 5 it contributes. ```java class Solution { public int trailingZeroes(int n) { int zeroCount = 0; // We only need to check multiples of 5. for (int i = 5; i <= n; i += 5) { int currentNum = i; // Count factors of 5 in the current number. // e.g., 25 has two factors of 5, 125 has three. while (currentNum > 0 && currentNum % 5 == 0) { zeroCount++; currentNum /= 5; } } return zeroCount; } } ``` This approach avoids the overflow issue and is significantly faster than the brute-force method. It's efficient enough to pass for the given constraints but can still be optimized. ### Algorithm - Initialize a counter `zeroCount` to 0. - Iterate through all numbers `i` from 5 to `n`. We can step by 5 since only multiples of 5 can contribute a factor of 5. - For each number `i`, we need to find out how many factors of 5 it contains. For example, 5 has one, 10 has one, but 25 has two. - Create a temporary variable `currentNum = i`. - While `currentNum` is greater than 0 and is divisible by 5, increment `zeroCount` and divide `currentNum` by 5. - After the loop finishes, `zeroCount` will hold the total number of factors of 5 in `n!`, which is the answer. ## Efficient Factor Counting in Logarithmic Time This is the most optimal approach, which stems from a mathematical insight. Instead of checking each number, we can count the factors of 5 more directly. The total number of factors of 5 in `n!` is the sum of the number of multiples of 5, the number of multiples of 25, the number of multiples of 125, and so on, up to `n`. **Time:** O(log n) · **Space:** O(1) **Pros:** Extremely fast and efficient.; Satisfies the follow-up question for a logarithmic time solution.; Elegant and concise. **Cons:** The underlying mathematical reasoning might not be immediately obvious without prior knowledge. ### Explanation This highly efficient method directly calculates the number of factors of 5 in `n!` without iterating through all numbers. The logic is as follows: - Every multiple of 5 contributes one factor of 5. There are `n/5` such numbers. - Every multiple of 25 contributes an additional factor of 5 (one was already counted in the `n/5` step). There are `n/25` such numbers. - Every multiple of 125 contributes yet another factor of 5. There are `n/125` such numbers. - We continue this process for all powers of 5 less than or equal to `n`. The total number of zeroes is `n/5 + n/25 + n/125 + ...` This can be implemented with a very concise loop. ```java class Solution { public int trailingZeroes(int n) { int count = 0; while (n > 0) { n /= 5; count += n; } return count; } } ``` Let's trace `n = 100`: 1. `count = 0`, `n = 100`. 2. `n = 100 / 5 = 20`. `count = 0 + 20 = 20`. 3. `n = 20 / 5 = 4`. `count = 20 + 4 = 24`. 4. `n = 4 / 5 = 0`. `count = 24 + 0 = 24`. 5. `n` is now 0, loop terminates. Result is 24. This approach is extremely fast and meets the follow-up requirement of a logarithmic time solution. ### Algorithm - The number of multiples of 5 up to `n` is `floor(n/5)`. Each of these contributes at least one factor of 5. - Numbers like 25, 50, 75 are multiples of 25. They contribute an *additional* factor of 5. The number of such numbers is `floor(n/25)`. - Numbers like 125 contribute yet another factor of 5. The number of such numbers is `floor(n/125)`. - This pattern continues for all powers of 5. - The total count is `count = floor(n/5) + floor(n/25) + floor(n/125) + ...` - This can be implemented with a simple loop. # Solutions ### Java ```java class Solution { public int trailingZeroes(int n) { int ans = 0; while (n > 0) { n /= 5; ans += n; } return ans; } } ``` ### CPP ```cpp class Solution { public: int trailingZeroes(int n) { int ans = 0; while (n) { n /= 5; ans += n; } return ans; } }; ``` ### Python ```python class Solution: def trailingZeroes(self, n: int) -> int: ans = 0 while n: n //= 5 ans += n return ans ```