172. Factorial Trailing Zeroes

MediumMath
Leetcode Link

Problem Description

Given an integer n, the objective is to calculate how many trailing zeroes are found in the factorial of n, noted as n!. The factorial of a number n is the product of all positive integers from 1 to n, inclusive. Trailing zeroes in this context refer to the number of zeroes that appear at the end of the number n! before any other digit appears.

Intuition

Trailing zeroes are created by the product of the factors 2 and 5. Since the factorial of any number n will have more factors of 2 than factors of 5, the number of trailing zeroes is determined by the number of times the factor 5 is included in the factorial.

Therefore, to count the number of trailing zeroes, we need to find out how many times the number 5 can fit into the factors of all numbers from 1 to n. This is done by dividing n by 5 and adding the quotient to the count of trailing zeroes. However, numbers that are powers of 5 (such as 25, 125, etc.) are counted multiple times because they contribute more than one factor of 5. For example, 25 is 5 * 5, so it contributes two factors of 5.

The solution approach is to iteratively divide n by 5 and add the quotient to a cumulative sum until n is zero. On each iteration, n is updated by dividing it by 5. This way, we account for additional factors of 5 contributed by powers of 5. The final sum is the number of trailing zeroes in n!.

Learn more about Math patterns.

Not Sure What to Study? Take the 2-min Quiz to Find Your Missing Piece：

Which of the two traversal algorithms (BFS and DFS) can be used to find whether two nodes are connected?

Solution Approach

The implementation of the solution leverages a simple iterative approach without the need for any complex data structures or algorithms. It makes use of basic arithmetic division and addition operations to determine the count of trailing zeroes.

Here's the step-by-step breakdown of the solution approach:

  1. Initialize a variable ans to 0 to hold the accumulated count of trailing zeroes.
  2. Enter a while loop that will continue to execute as long as n is not zero. Inside the loop:
    • Perform integer division of n by 5 and update n with the quotient. This is done using the // operator in Python which is the floor division operator. It returns the largest possible integer that is less than or equal to the division result. 
      1n //= 5
    • Add the updated value of n to ans. Since n was divided by 5, it now represents the number of additional factors of 5 that can be included from the updated range of numbers to n. 
      1ans += n
  3. After the loop terminates (when n is reduced to 0), ans will contain the total count of trailing zeroes in the factorial of the original n.
  4. Return ans as the final result.

By repeatedly dividing n by 5, the solution effectively accounts for all the factors of 5 present in the factorial of n. These factors are the ones responsible for contributing trailing zeroes since there are always sufficient factors of 2 to pair with them. This process takes into account not just the single multiples of 5 but also the multiples of higher powers of 5, which contribute more than one 5 to the factorial.

There are no additional patterns or complex algorithms used in this approach as the problem can be efficiently solved with this direct method.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

Which of the following problems can be solved with backtracking (select multiple)

Example Walkthrough

Let's walk through an example to illustrate the solution approach. Suppose we want to find the number of trailing zeroes in the factorial of n=10. The factorial of 10 is 10! = 10 x 9 x 8 x 7 x 6 x 5 x 4 x 3 x 2 x 1.

Following the steps in the solution approach:

  1. We initialize ans to 0. This will keep track of the number of trailing zeroes.

  2. We check how many times 10 can be divided by 5:

    • In the first iteration, 10 // 5 = 2. So, we set n to 2 and add 2 to ans. Now ans = 2.

  3. We continue the while loop with the updated value of n:

    • n is now 2, which is not zero, so we continue.
    • Now, 2 // 5 = 0. We set n to 0 (since 2 is less than 5, and using floor division, we get 0).
    • We add 0 to ans. This does not change ans, so it remains 2.

  4. The while loop ends because n is now 0.

  5. At the end, ans = 2, which means the factorial of 10 (10!) has 2 trailing zeroes.

This small example shows how the solution approach efficiently calculates the number of trailing zeroes of a factorial by considering the powers of 5 in n!. The process of dividing n by 5 and summing the quotients ensures we count each factor of 5 present in the factorial, leading to the correct number of trailing zeroes.

Solution Implementation

1class Solution:
2    def trailingZeroes(self, n: int) -> int:
3        # Initialize zeros count to 0
4        zeros_count = 0
5      
6        # Keep dividing n by 5 and update zeros count
7        while n:
8            n //= 5
9            zeros_count += n
10      
11        # Return the count of trailing zeros in n!
12        return zeros_count
13
1class Solution {
2    // This method calculates the number of trailing zeros in the factorial of a given number 'n'.
3    public int trailingZeroes(int n) {
4        int count = 0; // Initialize a counter to store the number of trailing zeros
5        while (n > 0) {
6            n /= 5; // Divide 'n' by 5, reducing it to the count of factors of 5
7            count += n; // Increment the count by the number of 5's factors in the current 'n'
8        }
9        return count; // Return the total count of trailing zeros
10    }
11}
12
1class Solution {
2public:
3    int trailingZeroes(int n) {
4        int count = 0; // Initialize count of trailing zeroes in factorial
5
6        // Loop to divide n by powers of 5 and add to the count
7        while (n > 0) {
8            n /= 5;      // Factor out the 5's, as 10 is the product of 2 and 5,
9                         // and there are always more 2's than 5's in factorial.
10            count += n;  // Accumulate the number of 5's in all factors of n
11        }
12
13        return count; // return the number of trailing zeroes in n!
14    }
15};
16
1// Calculates the number of trailing zeroes in the factorial of a given number
2// by counting the number of multiples of 5 in the factors of the numbers that compose the factorial.
3// This is because each pair of 2 and 5 contribute to a trailing zero, and there will always
4// be more multiples of 2 than 5, so we only count the multiples of 5.
5
6/**
7 * Calculates the number of trailing zeroes in n! (n factorial).
8 * 
9 * @param {number} n - The input number to calculate the factorial for.
10 * @returns {number} The number of trailing zeroes in n!.
11 */
12function trailingZeroes(n: number): number {
13    let zeroCount = 0; // Initialize the count of trailing zeros
14  
15    // Keep dividing n by 5 and update zeroCount to count 
16    // the factors of 5 in n! as each contributes to a trailing zero
17    while (n > 0) {
18        n = Math.floor(n / 5); // Divide n by 5
19        zeroCount += n; // Increment zeroCount by the quotient
20    }
21  
22    // Return the total count of trailing zeroes in n!
23    return zeroCount;
24}
25
Not Sure What to Study? Take the 2-min Quiz：

What's the output of running the following function using input 56?

1KEYBOARD = {
2    '2': 'abc',
3    '3': 'def',
4    '4': 'ghi',
5    '5': 'jkl',
6    '6': 'mno',
7    '7': 'pqrs',
8    '8': 'tuv',
9    '9': 'wxyz',
10}
11
12def letter_combinations_of_phone_number(digits):
13    def dfs(path, res):
14        if len(path) == len(digits):
15            res.append(''.join(path))
16            return
17
18        next_number = digits[len(path)]
19        for letter in KEYBOARD[next_number]:
20            path.append(letter)
21            dfs(path, res)
22            path.pop()
23
24    res = []
25    dfs([], res)
26    return res
27
1private static final Map<Character, char[]> KEYBOARD = Map.of(
2    '2', "abc".toCharArray(),
3    '3', "def".toCharArray(),
4    '4', "ghi".toCharArray(),
5    '5', "jkl".toCharArray(),
6    '6', "mno".toCharArray(),
7    '7', "pqrs".toCharArray(),
8    '8', "tuv".toCharArray(),
9    '9', "wxyz".toCharArray()
10);
11
12public static List<String> letterCombinationsOfPhoneNumber(String digits) {
13    List<String> res = new ArrayList<>();
14    dfs(new StringBuilder(), res, digits.toCharArray());
15    return res;
16}
17
18private static void dfs(StringBuilder path, List<String> res, char[] digits) {
19    if (path.length() == digits.length) {
20        res.add(path.toString());
21        return;
22    }
23    char next_digit = digits[path.length()];
24    for (char letter : KEYBOARD.get(next_digit)) {
25        path.append(letter);
26        dfs(path, res, digits);
27        path.deleteCharAt(path.length() - 1);
28    }
29}
30
1const KEYBOARD = {
2    '2': 'abc',
3    '3': 'def',
4    '4': 'ghi',
5    '5': 'jkl',
6    '6': 'mno',
7    '7': 'pqrs',
8    '8': 'tuv',
9    '9': 'wxyz',
10}
11
12function letter_combinations_of_phone_number(digits) {
13    let res = [];
14    dfs(digits, [], res);
15    return res;
16}
17
18function dfs(digits, path, res) {
19    if (path.length === digits.length) {
20        res.push(path.join(''));
21        return;
22    }
23    let next_number = digits.charAt(path.length);
24    for (let letter of KEYBOARD[next_number]) {
25        path.push(letter);
26        dfs(digits, path, res);
27        path.pop();
28    }
29}
30

Time and Space Complexity

The given Python code function trailingZeroes calculates the number of trailing zeros in the factorial of a given number n. The main idea behind the code is that trailing zeros are created by the pair of prime factors 2 and 5, and since there are more 2s than 5s in the factorial, the number of 5s will determine the number of trailing zeros.

The algorithm works by iteratively dividing n by 5 to count how many multiples of 5, 25, 125, etc., are there in n! (factorial of n), as each contributes to a trailing zero.

Time Complexity:

The time complexity is determined by the number of times n can be divided by 5. This loop runs approximately log5(n) times since we divide n by 5 in each iteration until n becomes 0. Each operation inside the loop takes constant time. Hence, the time complexity is O(log5(n)).

Space Complexity:

The space complexity of this algorithm is O(1), since we only need a fixed amount of space for the variable ans, no matter the size of the input n.

Learn more about how to find time and space complexity quickly using problem constraints.

Fast Track Your Learning with Our Quick Skills Quiz:

Depth first search can be used to find whether two components in a graph are connected.

Recommended Readings

Math Basics

Math for Technical Interviews How much math do I need to know for technical interviews The short answer is about high school level math Computer science is often associated with math and some universities even place their computer science department under the math faculty However the reality is that you

LeetCode Patterns - Top Patterns for Coding Interviews

Top Patterns to Conquer the Technical Coding Interview Should the written word bore you fear not A delightful video alternative awaits iframe width 560 height 315 src https www youtube com embed LW8Io6IPYHw title YouTube video player frameborder 0 allow accelerometer autoplay clipboard write encrypted media gyroscope picture in picture

Recursion Review

Recursion Recursion is one of the most important concepts in computer science Simply speaking recursion is the process of a function calling itself Using a real life analogy imagine a scenario where you invite your friends to lunch https algomonster s3 us east 2 amazonaws com recursion jpg You first

Got a question? Ask the Teaching Assistant anything you don't understand.

Still not clear? Ask in the Forum,  Discord or Submit the part you don't understand to our editors.

←
↑TA 👨‍🏫