Trailing zeros of n！

Posted on | In | Comments: | Views:

I. Problem

Count how many trailing ‘0’ for the result of n!

II. Solution

The 0 are only contributed by both factor 2 and 5, which means the number of trailing 0 equals the number of pairs of 2 & 5

Thus, we only need to find out how many times of the factor 2 and factor 5 in this n! is good enogh; and then min(num_2, num_5)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
// // Test
let res = trailing_zeros_for_factorial_of(5)
console.log(res)	// 1

res = trailing_zeros_for_factorial_of(8)
console.log(res)    // 1

res = trailing_zeros_for_factorial_of(10)
console.log(res)    // 2

res = trailing_zeros_for_factorial_of(15)
console.log(res)    // 3

function trailing_zeros_for_factorial_of(n){
    let num_2 = 0    
    let num_5 = 0
    
    let d = 5
    while(n >= d){
        num_5 += Math.floor(n / d)
        d *= 5 
    }
    
    d = 2
    while(n >= d){
        num_2 += Math.floor(n / d)
        d *= 2 
    }
    return Math.min(num_2, num_5)
}

III. Complexity

  1. Time: O(n)
  2. Space: O(1)