Find the number of trailing zeroes in a given factorial of n
Examples :
Input: 5
Output: 1
Explanation: A factorial of 5 is 120, so it had only 1 trailing zero.
Input: 10
Output: 2
Explanation: A factorial of 5 is 3628800, so it had only 2 trailing zeros.
Brute Force Approach
The brute force approach to this question is to find the factorial of the number and then count the number of trailing zeroes by repeatedly dividing it by 10 until we get a non-zero number in the ones place.
But to implement the brute force solution, first, we need to find the factorial of a number and then repeatedly divide it to count the number of zeroes.
For the small value of n where n! is less than equal to 1e18, the integer can fit in a 64-bit integer but for larger values, it can’t fit and will give us integer overflow.
So to avoid this integer overflow, we have to think up a different approach.
Optimized Approach
As we need to count the number of trailing zeroes we can say a trailing zero comes when a number is multiplied by 10, right?
So if we have a number num = 123
when it is multiplied by 10 it becomes 1230 (number of trailing zeros = 1), if we again multiply that number by 10 then it becomes 12300 (number of trailing zeros = 2).
So we can conclude that the number of trailing zeros is the number of times it is multiplied by 10.
So the number 10 forms when 5 is multiplied by 2 i.e. 10 = 5*2, we need to check how many pairs of 5 and 2 we can find to form 10’s.
In a number line, we can see that the multiple of the number 2 occurs after every alternate integer, and the multiple of the number 5 occurs after every 4 numbers.
I.e. if we have numbers 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20.
Multiple of 2: 2, 4, 6, 8, 10, 12, 14, 16, 18, 20. (10 times).
Multiple of 5: 5, 10, 15, 20. (4 times).
So we can say that if we represent a number in its prime factor, it can be represented as
num = 5^x * 2^y * a1^b1 * a2^b2 * a3^b3 * …..an^bn.
where x,y,b1,b2 ….bn are the exponents of the prime factors(2,5,a1,a2 ….an) respectively.
Here if we closely observe, we can observe that for any number n, we can see that x<y (x is the exponent raised to 5 and y is the exponent raised to 2).
So if we take the minimum of x and y, let's say z so the z number of times we can form the number 10.
i.e. min(x,y) = z , 5^z * 2^z = (5*2)^z = 10^z. As x<y.
The number z comes from the integer x(which is the power of 5).
So the number of trailing zeros in a number n is equal to n! / z.
Now let us understand with an example where n=24, so the number of occurrences of 5 in the prime factorization of 24! is 4.
In 24! Only a multiple of 5 will contribute to the count of 5, so each number 5, 10, 15, 20 will contribute to the count of 5 i.e. count = 4.
General formula , n/5
Now let's check for n = 25, so if we solve it the formula that we have derived above n/5 = 25/5 = 5.
But is it correct?
In 25!, according to the formula (n/5), each number 5, 10, 15, 20, and 25 will contribute 1 to the count but we can see it’s incorrect because we can write 25 as 5*5 so it will contribute 2 to the count.
So if we divide n/5 it will give us a count of 5 for each of the multiples of 5 i.e.(5,10,15,20,25) and when we divide it by 5^2 i.e. 25 it will give us the count of 1 for each multiple of 25 i.e. (25).
I.e. in total 1+1+1+1+2=6.
Now if we take another example 126 here the multiple of 126! Which will contribute to the count of 5 are
5, 10, 15, 20, 25, 30, 35, 40, 45, 50, 55, 60….125.
Where a multiple of 5 will contribute 1 to the count,
Similarly multiple of 5^2 = 25 i.e. 25,50,75,100,125 will contribute 2 to the count.
Similarly multiple of 5^3 = 125 i.e. 125 will contribute 3 to the count.
So in general if we want to find the count of 5 which occurs prime factorization of n! equal to
n! / (5^1) + n! / (5^2) + n! / (5^3) + ….0(till n!/(5^z) <=0 ).
Since we get the count of 5 from here it can form multiple 10 by multiplying it with an efficient number of 2.
Code Implementation
C++ Code Try on Compiler!
// Function to find the number of trailing zeroes in n!
int countTrailingZeroes(int n) {
// Initialize count of trailing zeroes
int count = 0;
// Iterate through powers of 5
for (int i = 5; n / i >= 1; i *= 5) {
// Add the count of multiples of the current power of 5
count += n / i;
}
// Return the total count of trailing zeroes
return count;
}Java Code Try on Compiler!
public class TrailingZeroes {
// Function to count trailing zeroes in n!
public static int countTrailingZeroes(int n) {
int count = 0; // Initialize count
for (int i = 5; n / i >= 1; i *= 5) {
count += n / i; // Count multiples of current power of 5
}
return count; // Return total count
}
}Python Code Try on Compiler!
# Function to count trailing zeroes in n!
def count_trailing_zeroes(n):
count = 0 # Initialize count
i = 5
while n // i >= 1:
count += n // i # Count multiples of current power of 5
i *= 5
return count # Return total countJavascript Code Try on Compiler!
// Function to count trailing zeroes in n!
function countTrailingZeroes(n) {
let count = 0; // Initialize count
for (let i = 5; Math.floor(n / i) >= 1; i *= 5) {
count += Math.floor(n / i); // Count multiples of current power of 5
}
return count; // Return total count
}Time Complexity : O(logn)
The number of divisions needed is proportional to the number of powers of 5 less than or equal to n.
The largest power of 5 less than n is 5^k, where 5k≤n. Solving 5k≤n gives k≈log5(n).
Therefore, the number of operations is O(log5n), which is effectively O(logn).
Space Complexity : O(1)
The space complexity of this algorithm is O(1). The algorithm uses a fixed amount of extra space regardless of the input size. It only requires a few variables (like the count, and loop counter), and the amount of memory needed does not grow with n.