In this tutorial, We are going to learn how to get total count trailing zeros in factorial of a number in o(n) time complexity in go golang and C language.
Example:
Input: 5
Factorial of 5: 120
Total trailing zeros: 1
--------------------------------------------------
Input: 23
Factorial of 23: 25852016738884976640000
Total trailing zeros: 4
--------------------------------------------------
Input: 15
Factorial of 15: 1307674368000
Total trailing zeros: 3
Mathematics formula to count trailing zeros in factorial of a number:
Trailing 0s in n! = floor(n/5) + floor(n/25) + floor(n/125) + ....
It will go till we get 0 after dividing n by multiple of 5
Eg:
Trailing 0s in 127! = floor(127/5) + floor(127/25) + floor(127/125)
= 25 + 5 + 1
= 31
Trailing 0s in 50! = floor(50/5) + floor(50/25)
= 10 + 2
= 12
Algorithm:
- Get input number
- Set index variable to 5
- Set count variable to 0
- Run loop from index number to input number
- In each iteration, Do divide input number by index number. Store the dividend into count variable. Increment index by multiple of 5
Code in go golang:
package main
import "fmt"
func main() {
var n int
fmt.Print("Enter the number: ")
fmt.Scan(&n)
var i int = 5
var count int = 0
for i <= n {
count = count + (n / i);
i = i * 5;
}
fmt.Printf("Total trailing zeros: %d", count)
}
Code in C language:
#include <stdio.h>
int main() {
int n;
printf("Enter the number: ");
scanf("%d", &n);
int count = 0, index;
for (index = 5; index <= n; index = index * 5) {
count = count + (n / index);
}
printf("\nTotal trailing zeros: %d", count);
}
Output:
Enter the number: 5
Total trailing zeros: 1
Enter the number: 23
Total trailing zeros: 4
Enter the number: 15
Total trailing zeros: 3
To learn more about golang, Please refer given below link:
https://techieindoor.com/go-lang-tutorial/
References:
https://golang.org/doc/
https://golang.org/pkg/
https://golang.org/pkg/fmt/
https://golang.org/pkg/fmt/#Println