## 编程知识 cdmana.com

### Two common factorial algorithms

172. Zero after factorial

793. After factorial K A zero

-----------

We often see factorial related questions in written examination questions , Today I'm going to talk about two of the most common topics ：

1、 Enter a non negative integer `n`, Please calculate the factorial `n!` There are several at the end of the result 0.

Like input `n = 5`, The algorithm returns 1, because `5! = 120`, There's one at the end 0.

The function signature is as follows ：

``````int trailingZeroes(int n);
``````

2、 Enter a non negative integer `K`, Please calculate how many `n`, Satisfy `n!` At the end of the result `K` individual 0.

Like input `K = 1`, The algorithm returns 5, because `5!,6!,7!,8!,9!` this 5 The result of factorials is only one 0, That is to say 5 individual `n` Meet the conditions .

The function signature is as follows ：

``````int preimageSizeFZF(int K);
``````

I put these two questions together , It must be because they have something in common , Let's analyze them one by one .

### Topic 1

It's definitely impossible to really do it `n!` The result of the calculation is , Factorial growth is more terrifying than exponential growth , Die as soon as possible .

that , At the end of the result 0 Where did you come from ？ Do we have an opportunistic way to figure out ？

First , When you multiply two numbers, you end up with 0, It must be because there are factors in two numbers 2 and 5, because 10 = 2 x 5.

in other words , Problem into ：`n!` How many factors can be decomposed at most 2 and 5

for instance `n = 25`, that `25!` At most, it can be broken down into several 2 and 5 Multiply ？ It depends on how many factors can be broken down 5, Because every even number can be decomposed into factors 2, factor 2 Definitely more than factor 5 A lot more .

`25!` in 5 Can provide a ,10 Can provide a ,15 Can provide a ,20 Can provide a ,25 There are two , All in all 6 A factor 5, therefore `25!` At the end of the result is 6 individual 0.

PS： I've seriously written about 100 Multiple original articles , Hand brush 200 Daoli is the subject , All published in labuladong A copy of the algorithm , Continuous updating . Recommended collection , Write the title in the order of my article , Master all kinds of algorithm set, then put into the sea of questions, like fish .

Now? , Problem into ：`n!` How many factors can be decomposed at most 5

The difficulty is like 25,50,125 Such a number , It can provide more than one factor 5, How can we not miss it ？

such , We assume that `n = 125`, Let's figure it out `125!` There are several at the end of the result 0：

First ,125 / 5 = 25, This step is to calculate how many images there are 5,15,20,25 these 5 Multiple , They must provide a factor 5.

however , Are these enough ？ Said just now , image 25,50,75 these 25 Multiple , You can provide two factors 5, Then we can work out `125!` There is 125 / 25 = 5 individual 25 Multiple , Each of them can provide an additional factor 5.

Is that enough? ？ We found that 125 = 5 x 5 x 5, image 125,250 these 125 Multiple , Can provide 3 A factor 5, Then we have to figure out again `125!` There is 125 / 125 = 1 individual 125 Multiple , It can also provide an additional factor 5.

This should be enough ,`125!` At most, it can be decomposed into 20 + 5 + 1 = 31 A factor 5, That is to say, at the end of the factorial result 31 individual 0.

Understand the idea , You can understand the code solution ：

``````int trailingZeroes(int n) {
int res = 0;
long divisor = 5;
while (divisor <= n) {
res += n / divisor;
divisor *= 5;
}
return res;
}
``````

here `divisor` Variable usage long type , Because if `n` The larger , consider while The end condition of the loop ,`divisor` There may be integer overflow .

The above code can be rewritten more simply ：

``````int trailingZeroes(int n) {
int res = 0;
for (int d = n; d / 5 > 0; d = d / 5) {
res += d / 5;
}
return res;
}
``````

such , This problem is solved , Time complexity is the base number is 5 The logarithmic , That is to say `O(logN)`, Let's take a look at how to complete the next problem based on the solution of this problem .

PS： I've seriously written about 100 Multiple original articles , Hand brush 200 Daoli is the subject , All published in labuladong A copy of the algorithm , Continuous updating . Recommended collection , Write the title in the order of my article , Master all kinds of algorithm set, then put into the sea of questions, like fish .

### The second question is

Now I'm going to give you a nonnegative integer `K`, How many `n`, bring `n!` At the end of the result `K` individual 0.

An intuitive solution to violence is exhaustion , Because with `n` An increase in ,`n!` It must be incremental ,`trailingZeroes(n!)` It must be increasing , The pseudo code logic is as follows ：

``````int res = 0;
for (int n = 0; n < +inf; n++) {
if (trailingZeroes(n) < K) {
continue;
}
if (trailingZeroes(n) > K) {
break;
}
if (trailingZeroes(n) == K) {
res++;
}
}
return res;
``````

above How to use binary search Said , For this monotonic function , use for Loop traversal , You can use binary search to reduce dimension , Right ？

How many searches `n` Satisfy `trailingZeroes(n) == K`, In fact, I am asking , Satisfied `n` What's the minimum , What's the biggest , Minus the maximum and minimum , You can figure out how many `n` The conditions are satisfied , Right ？ That's a binary search 「 Search the left border 」 and 「 Search the right border 」 These two things ？

Don't rush the code first , Because binary search needs to give a search range , The upper and lower bounds , In the above pseudo code `n` The lower bound is obviously 0, But the upper bound is `+inf`, How should this positive infinity be expressed ？

First , The positive infinity in mathematics can't be expressed programmatically , Our general approach is to use a very large value , It's too big to be taken . for instance int Maximum of type `INT_MAX`（2^31 - 1, about 31 Billion ）, If it's not enough long Maximum of type `LONG_MAX`（2^63 - 1, This value is too big to be true ）.

So how do I know how big it takes to 「 It must not be taken 」 Well ？ This requires reading the question carefully , Look at the range of data given in the title .

This topic is actually limited ,`K` Is in `[0, 10^9]` An integer in an interval , in other words ,`trailingZeroes(n)` At most, the result can reach `10^9`.

And then we can extrapolate , When `trailingZeroes(n)` The result is `10^9` when ,`n` How much? ？ You don't have to figure it out exactly , You just need to find a number `hi`, bring `trailingZeroes(hi)` Than `10^9` Big , You can put the `hi` As positive infinity , As the upper bound of the search interval .

Said just now ,`trailingZeroes` Functions are monotone functions , Then we can guess , Let's start with `trailingZeroes(INT_MAX)` Result , Than `10^9` Smaller , Then use `LONG_MAX` Calculate it , Far exceed `10^9` 了 , therefore `LONG_MAX` Can be used as the upper bound of search .

Note that in order to avoid integer overflow problems ,`trailingZeroes` Function needs to change all data types to long

``````//  Logic unchanged , Change the data type to  long
long trailingZeroes(long n) {
long res = 0;
for (long d = n; d / 5 > 0; d = d / 5) {
res += d / 5;
}
return res;
}
``````

Now the problem is clear ：

In the interval `[0, LONG_MAX]` In search of satisfaction `trailingZeroes(n) == K` The left and right boundaries of the .

According to the foregoing Binary search algorithm framework , You can search the left and right borders of the frame directly copy To come over ：

``````/*  The main function  */
int preimageSizeFZF(int K) {
//  The difference between the left and right borders  + 1  That's the answer.
return right_bound(K) - left_bound(K) + 1;
}

/*  Search for  trailingZeroes(n) == K  The left border of  */
long left_bound(int target) {
long lo = 0, hi = LONG_MAX;
while (lo < hi) {
long mid = lo + (hi - lo) / 2;
if (trailingZeroes(mid) < target) {
lo = mid + 1;
} else if (trailingZeroes(mid) > target) {
hi = mid;
} else {
hi = mid;
}
}

return lo;
}

/*  Search for  trailingZeroes(n) == K  On the right side of the border  */
long right_bound(int target) {
long lo = 0, hi = LONG_MAX;
while (lo < hi) {
long mid = lo + (hi - lo) / 2;
if (trailingZeroes(mid) < target) {
lo = mid + 1;
} else if (trailingZeroes(mid) > target) {
hi = mid;
} else {
lo = mid + 1;
}
}

return lo - 1;
}
``````

If you have any questions about the binary search framework , It is suggested to review the previous article Binary search algorithm framework , It's not going to unfold here .

Now? , This problem is basically solved , Let's analyze its time complexity .

The time complexity is mainly binary search , In terms of numbers `LONG_MAX` yes 2^63 - 1, Too big , But binary search is logarithmic complexity ,log(LONG_MAX) It's a constant ; It's called every two minutes `trailingZeroes` function , Complexity O(logK); So the overall time complexity is O(logK).

＿＿＿＿＿＿＿＿＿＿＿＿＿

my Online e-books Yes 100 Original articles , Hands with brushes 200 Daoli is the subject , Recommended collection ！ Corresponding GitHub Algorithm Repository We've got it 70k star, Welcome to mark star ！

Scroll to Top