Zero after factorial (C language)

Let's look at the description of the problem .

subject ： Given an integer n , return n! The number of trailing zeros in the result .

Input ：n = 3
Output ：0
explain ：3! = 6 , No trailing 0

Input ：n = 5
Output ：1
explain ：5! = 120 , There is a tail 0

Title source （ Power button ）： Zero after factorial

Topic analysis

Obviously , Directly calculate the factorial of an integer and then judge the trailing zero , Definitely not . Because if you are factoring a large integer , The result is very large , So that any type of variable used to store will generate overflow .

therefore , We have to Another angle To think about it . It's not hard to find out , When a positive integer is multiplied by 10 when , It will expand to the original 10 times , As a result, there is an additional trailing zero . But when calculating 5! when , Its result also has trailing zeros . So what caused it 5! The trailing zero in the result ？
Let's put 5! Let's expand the original formula of ,5! = 5 * 4 * 3 * 2 * 1 . You can find 5! contains 2 * 5, That is equivalent to 10.
In that case , Then we can put 10 To disassemble into 2 * 5, Analyze the problem from a smaller point of view .

Then enumerate the factorial of an integer , such as ：
15! = 15 * 14 * 13 * 12 * 11 * 10 * 9 * 8 * 7 * 6 * 5 * 4 * 3 * 2 * 1
15! = (3 * 5)*(2 * 7) * 13 *(2 * 6) * 11 *(2 * 5) * (3 * 3) * (2 * 4) * 7 *(2 * 3) * 5 *(2 * 2) * 3 * 2 * 1

（ Calculate in advance to know ,15! The number of trailing zeros of the result of is 3）
Further discovery , Every time 5 The number appears as a factor 5, Every time 2 The number appears as a factor 2, in other words , factor 2 The number of must be no less than the factor 5 The number of . In other words , Find a factor 5, And there must be a factor 2 Pair with it . In that case , We can Put the question （ seek n! The number of trailing zeros in the result of ） Convert to seek n! There are factors 5 What is the number of .

But , wait a moment ！ Think again ,n! There are factors 5 The number of only comes from every 5 The number of 1 Secondary factor 5 Do you ？
If it is to ask for 25! The number of trailing zeros in the result ？ Unfold it ,25! = 25 * 24 * 23 * … * 2 * 1.
among 25 = 5 * 5, That is to say, a number of factors may contain more than one 5 , such as 125! in 125 = 5 * 5 * 5 etc. .

There are rules ：
Every time 5 Number appears 1 Secondary factor 5,
Every time 25 Number appears 2 Secondary factor 5,
Every time 125 Number appears 3 Secondary factor 5,
…,
And so on .

Draw a picture and feel it intuitively ：

Every time 25 Number appears 2 Time 5, in other words , Every time 5 Add once to the number 5, Every time 25 Add one more time to the number 5.
And so on .

in other words factor 5 The number of be equal to n/5 + n/25 + n/125 …

But it's still an old problem , Not even when the denominator is large , Will cause overflow problems . So it's written as
whenever n/5 after , hold n Updated once .

It can be understood as ：

Code implementation

Then convert it into the following code ：

int trailingZeroes(int n){
    
    int cnt=0;   // Recording factor 5 The number of 
    while(n>0)
    {
    
       cnt+=n/5;
        n/=5;   // to update n
    }
    
    return cnt;
}

Test general examples , The result is right .
Consider the special case ：0! = 1 , The number of trailing zeros is 0.
Obviously, the result of the program running cnt = 0, Meet the conditions .

More articles
Adjust the array order so that the odd Numbers precede the even Numbers （C Language ）