Miscellaneous-Mixed-Programs/calculate-the-number-of-trailing-zeroes-of-the-factorial-of-a-number.cpp at 2026-files · SrishtiSaurav22/Miscellaneous-Mixed-Programs · 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
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
#include<bits/stdc++.h>
// #include"factorial-of-a-number.cpp"
/*
I can't simply include the above code file because I'm getting the following error:

    redefinition of 'int main()'
*/

using namespace std;

/*
The below function will potentially cause an integer overflow when the product of the multiplication operation being performed very quickly
exceedes the max value that "int" can store.

For a typical 32 bit signed integer:
Max value=2,147,483,647

In C/C++, signed integer overflow is undefined behaviour, so the result may become negative or garbage.
=> Program may still run but give incorrect results

So:
12! = 479001600   (fits)
13! = 6227020800  (exceeds int limit)

Now, we could use another data type like "long long", but it also has its limitations:

20! fits in long long
21! overflows
*/

/*
Below is an iterative function to calculate the factorial of a whole number

Time complexity:  theta(n)

Space complexity: theta(1)      (due to fixed number of total variables (input n, extra res), independent of input size)
Auxiliary space:  theta(1)      (due to fixed number of extra variables (res), independent of input size)
*/

int factorial_i(int n)
{
    int res=1;

    for(int i=2; i<=n; i++)
    {
        res=res*i;
    }

    return res;
}

/*
Below is an iterative function to calculate the number of trailing zeroes in the factorial of a whole number

Time complexity:  theta(n) + theta(log n) => theta(n)

Space complexity: theta(1)      (fixed number of total variables)
Auxiliary space:  theta(1)      (fixed number of extra variables)
*/

int calc_trailing_zeroes_in_fact(int n)
{
    int N=factorial_i(n), num=0;

    while(N%10==0)
    {
        ++num;
        N=N/10;
    }

    return num;
}

/*
Below is an optimized version of the iterative function to calculate the number of trailing zeroes in the factorial of a whole number

Time complexity:  theta(n)

Space complexity: theta(1)      (fixed number of total variables)
Auxiliary space:  theta(1)      (fixed number of extra variables)
*/

int calc_trailing_zeroes_in_fact_optimized(int n)
{
    if(n<5)
        return 0;

    int count=0;

    for(int i=5;i<=n;i+=5)
    {
        int N=i;
        while(N%5==0)
        {
            ++count;
            N/=5;
        }
    }

    return count;
}

/*
Below is an even further optimized version of the iterative function to calculate the number of trailing zeroes in the factorial of a
whole number

Time complexity:  theta(log n)

Space complexity: theta(1)      (fixed number of total variables)
Auxiliary space:  theta(1)      (fixed number of extra variables)
*/

int calc_trailing_zeroes_in_fact_optimized_further(int n)
{
    int res=0;

    for(int i=5;i<=n;i*=5)
        res=res+(n/i);

    return res;
}

int main()
{
    int n;

    cout<<"Enter a whole number: ";
    cin>>n;

    cout<<"\nThe number of trailing zeroes in the factorial of "<<n<<" is "<<calc_trailing_zeroes_in_fact_optimized(n);

    return 0;
}