编程知识 cdmana.com

Two common factorial algorithms

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

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 !

版权声明
本文为[labuladong,]所创,转载请带上原文链接,感谢

Scroll to Top