data-structures-and-algorithms-solutions/factorial-trailing-zeros.py at April-2020 · johnoyegbite/data-structures-and-algorithms-solutions · GitHub

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
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
# -*- coding: utf-8 -*-
"""
Created on Thu Jan 23 19:06:15 2020

@author: johnoyegbite
"""
# SOLVED!
"""
Problem:
    Given an integer n, return the number of trailing zeroes in n!.

Example1
    Input: n = 5
    Output: 1
    Explanation:
        1*2*3*4*5=120

Example2
    Input: n = 10
    Output: 2
    Explanation:
        1*2*3*4*5*6*7*8*9*10=3628800

Notice:
    Your solution should be in logarithmic time complexity.

"""

"""
Through research, the total number of trailing zeroes is the sum of the
geometric series:
    n/5^1 + n/5^2 + n/5^3 + ... + n/5^x

    where x is the power of 5 such that 5^x <= n.
    i.e. if n = 15 => x = 1
         if n = 25 => x = 2
         if n = 30 => x = 2

"""


def trailingZeroes(n):
    # write your code here
    n_per_fives = 0
    five_power = 1
    while (n // 5**five_power) > 0:
        n_per_fives += (n // 5**five_power)
        five_power += 1

    return n_per_fives


if __name__ == "__main__":
    n = 454543
    print(trailingZeroes(n))