I’m sure you know how to do n factorial if you know the definition of factorial, but if you’re in an interview and they throw you a seemingly simple algorithmic problem related to factorial, you’re not going to be able to give an elegant answer! This article will share several factorials related cases with increasing difficulty.

Case a

Given an integer N, then N factorial N! How many zeros are there at the end? For example, if N is 10, N! = 3628800, so N factorial There are two zeros at the end of.

Some people think, well, that’s not easy, just figure out N factorial. And then divide by 10 to see how many zeros there are.

Some people think, well, let’s just do N factorial. If you multiply a number by 10, you must have a zero at the end of the number. So, we can start from “which numbers can be multiplied to get 10”.

That’s right. It takes 2 times 5 to produce 10.

Notice, 4 times 5 is 20, which is also 0, but we can also factor 20, which is 10 times 2.

So the problem becomes N factorial. How many pairs of 2*5 can species be decomposed into? A further analysis will find that N! There must be more numbers divisible by 2 than by 5, so the problem becomes finding 1… N How many of these n numbers are divisible by 5? Notice, like 25 is divisible by 5 twice, so 25 is going to produce 2 pairs of 2 times 5 drops. With that in mind, the code looks like this:

int f(int n){
    int sum = 0;
    for(int i = 1; i <= n; i++){
        int j = i;
        while(j % 5 == 0){ sum++; j = j / 5; }}return sum;
}
Copy the code

Some people have come up with this pattern, and they’re very proud of it, but that’s not the answer the interviewer is looking for, so think of a question,

How many fives can be produced from 1 to 20 when N = 20? It’s 4, so N over 5 is equal to 4.

How many fives can be produced from 1 to 24 when N = 24? It’s 4, so N over 5 is equal to 4.

How many fives can be produced from 1 to 25 when N = 25? Six, mainly because 25 contributes two 5’s, so N over 5 plus N over 5 squared is equal to 6.

…

Sum = N/5 + N/5^2 + N/5^3+… .

So, the most elegant way to write this would be:

int f(int n){
    int sum = 0;
    while(n! = 0){ sum += n / 5; n = n / 5; }}Copy the code

At this point, you can be confident that you’re throwing code at the interviewer.

Case 2

O N! The least significant position of 1 in the binary representation of. For example, 3! =6, binary is 1010, so the lowest 1 is in the second place.

No ideas? Think carefully about how this problem relates to the previous one!

If you think about it, isn’t this also how many zeros are at the end? You know where the 1 is when you figure out how many zeros there are at the end, but this is how many zeros there are at the end of binary.

It’s binary, so every time you multiply it by 2 you get a 0 at the end.

So, just like the previous problem, N factorial. How many 2’s there are. I thought, fortunately, I made a similar one, so a wave of operation like a tiger, wrote the code in a minute:

int f(int n){
    int sum = 0;
    while(n! = 0){ sum += n / 2; n = n / 2; }}Copy the code

Interviewer: Can it be optimized?

What the hell? Also in the optimization? I’m in order logn time.

Remember I talked a little bit about bitwise operations? This problem can really be optimized with bits, divided by n / 2 == n >> 1. However, bitwise operations are much faster, so the optimized code looks like this:

int f(int n){
    int sum = 0;
    while(n! = 0){ n >>= 1; sum += n; }}Copy the code

Can you still optimize it?

Yeah, but I’m not going to do that, because I think that’s pretty fast. Maybe we’ll come back to this problem when we do other problems.

If you can write code like this, it’s pretty cool.

Case 3

Give you a number N, print N! The value of the.

Yeah, it’s that simple. I just want you to evaluate the factorial.

At this time, you have to be careful, do not wave operation

long long sum = 1;
for(int i = 1; i <= n; i++){
    sum *= i;

}
Copy the code

A for loop, done in a second.

Since you don’t know the range of n, you may also overflow if you use “long”, so at this time you should ask the interviewer whether the range of N is limited.

Interviewer: There is no limit!

Now, this factorial problem, which, to be honest, I’m sure most people haven’t done. So, today I’m going to take you to implement it, just in case you do get asked. Results the most familiar problem immediately do not know how to start.

In that case, we’re going to have to store the value in a string, and we’re going to have to multiply the value in a string, which means we’re going to multiply two large integers.

Let’s first implement a function that multiplies two large integers. An easy way to do this, like we did in elementary school, is to multiply the units digit times the other number of another number, and then multiply the tens digit times the other number of another number, and then add them.

The implementation code is as follows:

Public static String mul(String s1, String s2) {public static String mul(String s1, String s2) { char[] c1 = s1.toCharArray(); char[] c2 = s2.toCharArray(); int len = c1.length + c2.length; // Is used to store the product of two numbers'\u0000'Char [] c = new char[len]; // Since the low value of a large integer is at the end of the string, we count from the endfor(int i = c1.length - 1; i >= 0; i--) { int index = len - 1; int res = 0; // Use it to store the carryfor (int j = c2.length - 1; j >= 0; j--) {
                int temp = (c1[i]-'0') * (c2[j]-'0') + c[index] + res; res = temp / 10; c[index--] = (char)(temp % 10); } // Each carry is saved. c[index] = (char)res; len--; } // Finally add the characters in c'0'
        for (int i = 0; i < c.length; i++) {
            c[i] += '0'; } String s = new String(c); // If c[0] is 0, discard it if it is 0.if(c[0] == '0')
            return s.substring(1);
        else
        return s;
    }
Copy the code

Note, must be implemented again, must be implemented again, because the principle is simple, but manual implementation is not necessarily so simple, prone to bugs.

This way, it takes O(n) to multiply two large integers, but there’s a faster way, which is O(n^1.6), but the code is a little bit complicated.

Now that we know how to multiply two big integers, we can take our factorial, and we can do it, and every time we multiply, we just multiply it as if it were two big integers. The code is as follows:

Public static String f(int N) {String s ="1";
        Integer t = null;
        for(int i = 2; i <= n; i++) { t = i; Mul (s, t.tostring ()); }returns; } public static String mul(String s1, String s2) {public static String mul(String s1, String s2) { char[] c1 = s1.toCharArray(); char[] c2 = s2.toCharArray(); int len = c1.length + c2.length; // Is used to store the product of two numbers'\u0000'Char [] c = new char[len]; // Since the low value of a large integer is at the end of the string, we count from the endfor(int i = c1.length - 1; i >= 0; i--) { int index = len - 1; int res = 0; // Use it to store the carryfor (int j = c2.length - 1; j >= 0; j--) {
                int temp = (c1[i]-'0') * (c2[j]-'0') + c[index] + res; res = temp / 10; c[index--] = (char)(temp % 10); } // Each carry is saved. c[index] = (char)res; len--; } // Finally add the characters in c'0'
        for (int i = 0; i < c.length; i++) {
            c[i] += '0'; } String s = new String(c); // If c[0] is 0, discard it if it is 0.if(c[0] == '0')
            return s.substring(1);
        else
        return s;
    }
Copy the code

The time is order n^3. If you’re going to optimize, you’re going to optimize mostly in the multiplication of large integers.

conclusion

Doesn’t it feel like factorials aren’t that easy anymore? These three problems related to factorial, should be relatively common problems, today with you to share a wave, I hope you have the time to use their own code to implement, especially to calculate N! . I will continue to share with you some good algorithm problems and some algorithm techniques, please pay attention.