# Solution by ajitzero [3 approaches]

• #### Approach #1 Brute force [Integer Overflow]

Intuition

According to the question, we first calculate the factorial of the number and then count the number of zeroes from the last digit (least significant bit) until we get a non-zero digit.

Algorithm

• Use a simple loop to compute the factorial by multiplying all numbers in the range \$\$1 to n\$\$.
• Keep incrementing a counter variable, \$\$count\$\$ while the last digit is zero.

C++

``````    class Solution {
public:
int trailingZeroes(int n) {
long long int factorial = 1;
for (int i = 1; i <= n; ++i) {
factorial *= i;
}
int count = 0;
while (factorial % 10 == 0) {
++count;
factorial /= 10;
}
return count;
}
};
``````

Python

``````    class Solution(object):
def trailingZeroes(self, n):
res = 1
for i in xrange(1, n+1):
res *= i
count = 0
while res % 10 == 0:
count += 1
res /= 10
return
``````

Complexity Analysis

• Time complexity : \$\$O(n + count) = O(n)\$\$. To compute the factorial we need at most \$\$n\$\$ iterations and then we count the trailing zeroes, which takes at most \$\$count\$\$ iterations. Thus, the time complexity is \$\$O(n)\$\$.

• Space complexity : \$\$O(1)\$\$. We only need two variables for the factorial value and the counter variable.

Note

• For languages like Python which support arbitrarily large numbers, instead of encountering an integer overflow issue we face the Time Limit Exceeded error.
• The factorial of a non-negative number \$\$n\$\$, denoted by \$\$n!\$\$, is the product of all positive integers in the inclusive range of \$\$1 to n\$\$. By convention, factorial of zero, \$\$0!\$\$ is \$\$1\$\$ and is undefined for negative numbers. For the purposes of this problem, we extend the convention of using 1 as the result for non-negative numbers.

#### Approach #2 Mathematical simplification (Recursive) [Accepted]

Intuition

The number of trailing zeroes in \$\$n!\$\$ is the number of times \$\$10\$\$, i.e., \$\$2 * 5\$\$ is multiplied. Thus, we simply count all multiple of 5 less than or equal to \$\$n\$\$.

Example:

For \$\$1234!\$\$,

• \$\$1234 / 5\$\$ gives \$\$246\$\$ multiples of 5.
• \$\$246 / 5\$\$ gives \$\$49\$\$ multiples of 5.
• \$\$49 / 5\$\$ gives \$\$9\$\$ multiples of 5.
• \$\$9 / 5\$\$ gives \$\$1\$\$ multiples of 5.

Thus, we compute and get \$\$246 + 49 + 9 + 1 = 305\$\$ trailing zeros.

Algorithm

• Let `trailingZeroes(n)` be a function.
• If \$\$n\$\$ is zero, no more multiples of \$\$5\$\$ are left and return \$\$0\$\$.
• While \$\$n\$\$ is not zero, return the sum of \$\$n/5\$\$ (current multiples) and the result of `trailingZeroes(n/5)` (remaining multiples).

C++

``````    class Solution {
public:
int trailingZeroes(int n) {
if (n == 0) {
return 0;
}
return n / 5 + trailingZeroes(n / 5);
}
};
``````

Python

``````    class Solution(object):
def trailingZeroes(self, n):
if n == 0:
return 0
return n / 5 + self.trailingZeroes(n / 5)
``````

Complexity Analysis

• Time complexity : \$\$O(log(n))\$\$. Division by 5 reduces the number of operations taking place for every power of 5. Thus, the time complexity is \$\$O(log(n))\$\$.

• Space complexity : \$\$O(log_5(n))\$\$. Every recursive call is stored in a stack frame and thus, the space complexity is \$\$O(log(n))\$\$.

#### Approach #3 Mathematical simplification (Iterative) [Accepted]

Algorithm

• Initialize \$\$ans\$\$ to \$\$0\$\$.
• While \$\$n\$\$ is not less than \$\$5\$\$:
• Divide \$\$n\$\$ by \$\$5\$\$ and update it.

C++

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

Python

``````    class Solution(object):
def trailingZeroes(self, n):
count = 0
while n >= 5:
n /= 5
count += n
return count
``````

Complexity Analysis

• Time complexity : \$\$O(log(n))\$\$. Division by 5 reduces the number of operations taking place for every power of 5. Thus, the time complexity is \$\$O(log(n))\$\$.

• Space complexity : \$\$O(1)\$\$. We only need one variable for the counter variable.

Reference

Analysis written by @ajitzero

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.