Python Program to Count trailing zeroes in factorial of a number
Given an integer n, write a function that returns the count of trailing zeroes in n!
Examples :
Input: n = 5 Output: 1 Factorial of 5 is 120 which has one trailing 0. Input: n = 20 Output: 4 Factorial of 20 is 2432902008176640000 which has 4 trailing zeroes. Input: n = 100 Output: 24
Trailing 0s in n! = Count of 5s in prime factors of n! = floor(n/5) + floor(n/25) + floor(n/125) + ....
Method 1:
Python3
# Python3 program to # count trailing 0s # in n ! # Function to return # trailing 0s in # factorial of n def findTrailingZeros(n): # Initialize result count = 0 # Keep dividing n by # powers of 5 and # update Count i = 5 while (n / i > = 1 ): count + = int (n / i) i * = 5 return int (count) # Driver program n = 100 print ( "Count of trailing 0s " + "in 100 ! is" , findTrailingZeros(n)) |
Count of trailing 0s in 100 ! is 24
Time Complexity: O(log5n)
Auxiliary Space: O(1)
Please refer complete article on Count trailing zeroes in factorial of a number for more details!
Method 2: Using math.factorial() and for loop
Python3
# Python3 program to # count trailing 0s # in n ! # Function to return # trailing 0s in # factorial of n def findTrailingZeros(n): import math c = 0 x = math.factorial(n) s = str (x) a = s[:: - 1 ] for i in a: if (i ! = "0" ): break else : c + = 1 return c # Driver program n = 100 print ( "Count of trailing 0s " + "in 100 ! is" , findTrailingZeros(n)) |
Count of trailing 0s in 100 ! is 24
Time complexity: O(n)
Space complexity: O(n)
Method 3: Using recursion
Follow the steps below:
- The function countTrailingZeroes takes the parameter n and a count variable count which is initialized to 0.
- If n is equal to 0, the function returns the count variable. This is because there are no more numbers to check for multiples of 5.
- If n is not equal to 0, the function updates the count variable by dividing n by 5 and adding the result to the count variable.
- The function then calls itself, this time with n divided by 5 and the updated count variable as parameters.
- The main function initializes the n variable and calls the countTrailingZeroes function, storing the result in the result variable.
- Finally, the main function prints out the number of trailing zeros in n!.
Python3
def countTrailingZeroes(n, count = 0 ): if n = = 0 : return count else : count + = n / / 5 return countTrailingZeroes(n / / 5 , count) def main(): n = 100 result = countTrailingZeroes(n) print ( "The number of trailing zeros in %d! is %d" % (n, result)) if __name__ = = '__main__' : main() |
The number of trailing zeros in 100! is 24
Time complexity: O(log n). This is because in each recursive call, the value of n is divided by 5 until it becomes 0. Hence, the number of recursive calls is proportional to log n to the base 5.
Auxiliary space: O(log n) as well, because of the number of function calls required for the recursive function.
Method 4: Using Iterative method
Use a while loop to count the number of multiples of 5, starting from 5, and then multiplies the current count by 5 to count the next power of 5. The loop continues until the current power of 5 is greater than n. Finally, the function returns the total count of powers of 5, which corresponds to the number of trailing zeros in n!.
Python3
import math def findTrailingZeros(n): # count powers of 5 in prime factorization trailing_zeros = 0 i = 5 while i < = n: trailing_zeros + = n / / i i * = 5 return trailing_zeros # Driver program n = 100 print ( "Count of trailing 0s " + "in 100 ! is" , findTrailingZeros(n)) |
Count of trailing 0s in 100 ! is 24
Time complexity: O(log n)
Auxiliary space: O(1)
Contact Us