Factorial Trailing Zeroes LeetCode Solution

Difficulty Level Medium
Frequently asked in Amazon Bloomberg ByteDance Facebook Microsoft OracleViews 1884

Problem Statement

Factorial Trailing Zeroes LeetCode Solution – Given an integer n, return the number of trailing zeroes in n!.

Note that n! = n * (n - 1) * (n - 2) * ... * 3 * 2 * 1.

Input: n = 3
Output: 0
Explanation: 3! = 6, no

trailing zero

.

Input: n = 5
Output: 1
Explanation: 5! = 120, one trailing zero.

Explanation

This question is pretty straightforward.

Because all trailing 0 is from factors 5 * 2.

But sometimes one number may have several 5 factors, for example, 25 have two 5 factors, 125 have three 5 factors. In the n! operation, factor 2 is always ample. So we just count how many 5 factors are in all numbers from 1 to n.

So, if we take all the numbers with 5 as a factor, we’ll have way more than enough even numbers to pair with them to get factors of 10

Example One

How many multiples of 5 are between 1 and 23? There are 5, 10, 15, and 20, for four multiples of 5. Paired with 2’s from the even factors, this makes for four factors of 10, so: 23! has 4 zeros.

Example Two

How many multiples of 5 are there in the numbers from 1 to 100?

because 100 ÷ 5 = 20, so, there are twenty multiples of 5 between 1 and 100.

but wait, actually 25 is 5×5, so each multiple of 25 has an extra factor of 5, e.g. 25 × 4 = 100, which introduces an extra of zero.

So, we need to know how many multiples of 25 are between 1 and 100? Since 100 ÷ 25 = 4, there are four multiples of 25 between 1 and 100.

Finally, we get 20 + 4 = 24 trailing zeroes in 100!

The above example tells us, we need to care about 5, 5×5, 5×5×5, 5×5×5×5 ….

Example Three

By given number 4617.

5^1 : 4617 ÷ 5 = 923.4, so we get 923 factors of 5

5^2 : 4617 ÷ 25 = 184.68, so we get 184 additional factors of 5

5^3 : 4617 ÷ 125 = 36.936, so we get 36 additional factors of 5

^4 : 4617 ÷ 625 = 7.3872, so we get 7 additional factors of 5

5^5 : 4617 ÷ 3125 = 1.47744, so we get 1 more factor of 5

5^6 : 4617 ÷ 15625 = 0.295488, which is less than 1, so stop here.

Then 4617! has 923 + 184 + 36 + 7 + 1 = 1151 trailing zeroes.

Code

C++ Code for Factorial Trailing Zeroes

int trailingZeroes(int n) {
        return n == 0 ? 0 : n/5 + trailingZeroes(n/5);
    }

Java Code for Factorial Trailing Zeroes

public int trailingZeroes(int n) {
        return n == 0 ? 0 : n/5 + trailingZeroes(n/5);
    }

Python Code for Factorial Trailing Zeroes

def trailingZeroes(self, n: int) -> int:
        return 0 if n == 0 else n / 5 + self.trailingZeroes(n / 5)

Complexity Analysis for Factorial Trailing Zeroes LeetCode Solution

Time Complexity

O(log n) (Base 5)

Space Complexity

O(1)

Reference: https://en.wikipedia.org/wiki/Factorial

https://en.wikipedia.org/wiki/Trailing_zero

Translate »