Trailing Zeros in Factorial

Input: n = 5
Output: 1
Explaination: 1 * 2 * 3 * 4 * 5 = 120. We have one trailing zero in 120

Input: n = 10
Output: 2
Explaination: 1 * 2 * 3 * 4 * 5 * 6 * 7 * 8 * 9 * 10 = 3628800. We have two trailing zero in 3628800

Input: n = 100
Output: 24
Explaination: 1 * 2 * 3 * 4 * 5 ..... 98 * 99 * 100 = 93326215443944152681699238856266700490715968264381621468592963895217599993229915608941463976156518286253697920827223758251185210916864000000000000000000000000. We have 24 trailing zero in this number

Naive Approach

package main

import "fmt"

func main() {
    res := trailingZeroInFact(10)
    fmt.Println(res)
}

func trailingZeroInFact(n int) int {
    fact := 1
    for i := 2; i <= n; i++ {
        fact = fact * i
    }
    res := 0
    for fact%10 == 0 {
        res++
        fact = fact / 10
    }
    return res
}

Time Complexity: θ(n)

Dry Run:

n = 10
fact = 3628800
res = 0
After 1st iteration: res = 1, fact=362880
After 2nd iteration: res = 2, fact=36288

Limitation:

Causes value overflow for even for slightly higher value. Ex: n = 21, the factoring will be 20 digits. So it will be larger than int value in golang.

Trailing Zeros in Factorial

Naive Approach

Efficient Approach