1, n factorial

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.

Let me give you a code to taste, in detail

int f(n){
	return n == 0 ? 0 : n / 5 + f(n / 5);
}
Copy the code

For this problem, the normal operation is to just calculate N factorial. If you multiply a number by 10, it must produce a zero at the end of the number. Can you start by looking at which numbers you can multiply to get 10?

A: Yes, and only 2 times 5 produces 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 roughly converts to finding 1… N How many of these n numbers are divisible by 5,

Note that like 25 is divisible twice by 5, so 25 is capable of producing 2 pairs of 2 * 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

However, further unpacking, we found that

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, one line of code will do it

int f(n){
	return n == 0 ? 0 : n / 5 + f(n / 5);
}
Copy the code

Don’t ask. Ask is a line of code.

Two, two to the power

Determine whether an integer n is a power of 2

So the normal thing to do in this case is to keep dividing this number by 2, and see if there’s a remainder, until n is divisible into 1.

We can treat n as binary, if n is a power of two, then the highest binary bit of n is 1, followed by 0, for example, for 16, which is 10000.

If we subtract it by 1, it causes the highest bit to be 0 and all the rest to be 1, for example 10,000-1 = 01111.

Then we take n and (n-1), and the result will be 0, for example (assuming n is 16).

N & (n-1) = 10000 & (10000 -1) = 10000 & 01111 = 0

In other words, if n is a power of 2, then n & (n-1) is 0, otherwise it is not, so the code is as follows

int isPow(n){
	return (n & (n - 1)) == 0;
}
Copy the code

One line of code, one line of code, one line of code, one line of code

3. Find a number that is not repeated

You are given a set of integer numbers, in which one number appears only once and the others appear twice, and you are asked to find a number.

This is a problem that a lot of people might store in a hash table, and each time you store it, you keep track of how many times that number occurs, and then you iterate over the hash table to see which number occurs only once. This method is O(n) in time and O(n) in space.

However, I want to tell you that using bit operations to do, absolutely high force lattice!

We just said that the result of two identical numbers is 0, and the result of a number and 0 is itself, so let’s take the whole set of integers as xOR, for example: 1, 2, 3, 4, 5, 1, 2, 3, 4. Five of them only appeared once, the others all appeared twice, and the result was as follows:

Since xOR supports the commutative and associative laws, so:

123451234 = (11)(22)(33)(44)5= 00005 = 5.

In other words, the number that appears twice and then becomes zero, the number that appears once and then equals itself. Is this solution awesome? So here’s the code

int find(int[] arr){ int tmp = arr[0]; for(int i = 1; i < arr.length; i++){ tmp = tmp ^ arr[i]; } return tmp; }Copy the code

It’s O(n) in time, O(1) in space, and it looks pretty cool. Is this wave stable?

And just to illustrate, this works for an odd number of times, and an even number of other numbers

No, I have to keep pretending!

? The one-line solution is as follows:

// For example, when using this function, we initially pass I 1, Find (arr, 1, arr[0]) int find(int[] arr,int I,int result){return arr.length <= I? result : find(arr, i + 1, result ^ arr[i]); }Copy the code

In fact, this problem with a line of code, more complex + difficult to understand ，，，，，， sorry, I was wrong, should not be a simple problem complicated and then thrown to the interview question.

Original link: blog.csdn.net/m0\_3790779…

Three things to watch ❤️

If you find this article helpful, I’d like to invite you to do three small favors for me:

1. Like, forward, with your “like and comment”, is the power of my creation.

2. Follow the public account “Wish heaven has no BUG” and share original knowledge from time to time. Also look forward to the follow-up article ing

3. Reply [Learning] scan the code to obtain the learning materials package