172 Factorial Trailing Zeroes
Given an integern, return the number of trailing zeroes inn!.
Note:Your solution should be in logarithmic time complexity.
The Idea: First lets take a look at the factorial sequence and see if we can notice a pattern.
0 1
1 1
2 2
3 6
4 24
5 120
6 720
7 5040
8 40320
9 362880
10 3628800
11 39916800
12 479001600
13 6227020800
14 87178291200
15 1307674368000
16 20922789888000
17 355687428096000
18 6402373705728000
19 121645100408832000
20 2432902008176640000
21 51090942171709440000
22 1124000727777607680000
23 25852016738884976640000
24 620448401733239439360000
25 15511210043330985984000000
26 403291461126605635584000000
27 10888869450418352160768000000
If we just count the zeros we can see that it follows to be 0,0,0,0,0,1,1,1,1,1,2,2,2,2,2 .... and so fourth. That alone can be modeled with a linear function,
f(x) = floor(x/5)
However, there is one additional thing. Notice how there is a jump of an additional zero on
25!. It will follow that every 5^n there will be another one of this jumps, and they add on to the previous, we can fix our model now to be f(x) = floor(x/5) + floor(x/25)
But to get this right, we will need to add
floor(x/pow(5,n) dependently on just how large n actually gets.f(x) = floor(x/5) + floor(x/25) + floor(x/125) + ....+ floor(x/pow(5, n)) is the true solution.Complexity: Because our power number will expand exponentially, we will reach our target in logarithmic time, and so there will only be a logarithmic amount of summations. O(logn) time and space, but O(1) space iterative
Recursive
import math
class Solution:
def trailingZeroes(self, n):
"""
:type n: int
:rtype: int
"""
if n <= 4:
return 0
elif n <= 9:
return 1
return math.floor(n / 5) + self.trailingZeroes(math.floor(n / 5))
Iterative
import math
class Solution:
def trailingZeroes(self, n):
"""
:type n: int
:rtype: int
"""
five_pow = 1
current_power = math.pow(5, five_pow)
total_zeros = 0
while current_power <= n:
total_zeros += math.floor(n/current_power)
five_pow += 1
current_power = math.pow(5, five_pow)
return total_zeros
Last modified 3yr ago