After reading this article , You can go and get the following questions ：

**-----------**

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 ！