What’s the best thing to do during the long Spring Festival holiday? Of course is to toss about some algorithm problems, the following to tell you a few line of code can solve the algorithm problems, of course, I believe that these algorithm problems you have done, but even if done, but also can take a look, after all, you had a large probability is not a line of code to solve.

Learned a line of code to solve, later encounter the interviewer asked, you can install force.

One, 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

Two, one line of code to solve the classic Joseph ring

Joseph’s ring problem, which I’m sure you’ve seen in your freshman year and sophomore year, and many of you use as an application of circular lists, but circular lists are not the optimal solution, so TODAY I’m going to do it in one line of code, and it’s almost optimal.

In view of the fact that some people forget this question, I would like to post a description of this question

Problem description: N soldiers numbered 1-N sit together to form a circle, and count the numbers from the soldiers numbered 1 in turn (1, 2, 3… The soldier counting to m will be killed and the next soldier will count from 1. Until you have one soldier left, and you get that soldier’s number.

Give the code first and explain it later.

int f(int n, int m){
    return n == 1 ? n : (f(n - 1, m) + m - 1) % n + 1;
}
Copy the code

It works like this:

If we delete the soldiers and re-number the soldiers, then there is some mathematical relationship between the numbers before and after deletion, and we just need to find out the relationship.

We define the recursive function f(n, m) to return the number of the surviving soldier, and obviously f(n, m) = 1 when n = 1. If we can figure out the relationship between f(n, m) and f(n minus 1, m), we can do it recursively. Let’s say the number of people is n, and the person who counts to M commits suicide. The initial number is

… 1… m – 2

m – 1

m

m + 1

M + 2… N…

After a delete, node M is deleted. After deletion, there are only n-1 nodes left, and the conversion relationship between the numbers before and after deletion is as follows:

Before deleting — after deleting

… -…

m – 2 — n – 2

m – 1 — n – 1

M —- None (because the number was removed)

M + 1 — 1(because I’m counting from here next time)

m + 2 —- 2

… -…

The new ring has only n minus 1 nodes. Nodes numbered M + 1, M + 2, and M + 3 before deletion become nodes numbered 1, 2, and 3 after deletion.

Assuming that old is the node number before deletion and new is the node number after deletion, the relationship between old and new is old = (new + m-1) % n + 1.

So that gives us the relationship between f(n, m) and f(n minus 1, m), and f(1, m) = 1. So we can do it recursively. The code is as follows:

Old = (new + m) % n Mainly because the numbers start at 1, not 0. If new + m == n, the result will be old = 0. So old = (new + m – 1) % n + 1.

int f(int n, int m){
    if(n == 1)   return n;
    return (f(n - 1, m) + m - 1) % n + 1;
}
Copy the code

Why not one line but two? If you do this a lot, you want your code to look as short and brief as possible, but will it get harder to understand? I’m lazy, so here’s the code

int f(int n, int m){
    return n == 1 ? n : (f(n - 1, m) + m - 1) % n + 1;
}
Copy the code

Of course, I wrote a previous article that used three methods to solve the Joseph ring problem, if you are interested: Remember an Ali pen test: How do I solve the Joseph ring problem with one line of code

It’s a number that only appears once

Problem description: give you an integer array, the array has a number only appears once, the other numbers appear twice, find this number only appears once.

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, this problem can be solved by xOR operation. The result of two identical numbers xor is 0, and the result of a number and 0 xor is itself, and the xor operation supports the commutative law. Based on this characteristic, we just need to xOR all of this set of integers, and the final result is the number we are looking for.

For example, the data set is: 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:

1 ^ 2 ^ 3 ^ ^ 4 5 ^ 1 ^ 2 ^ 3 ^ 4 = ^ ^ 1 (1) (2 ^ 2) ^ ^ (3 ^ 3) (4 ^ 4) 5 = 0 ^ ^ ^ ^ ^ 0 0 0 5 = 5.

In this way, the space complexity can be reduced to O(1), while the time complexity remains the same. The corresponding code is shown below

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

What about the line of code we agreed on?

Isn’t that supposed to get through to you first? The one-line solution is as follows:

For example, when using this function, we initially pass the value of I to 1 and result to arr[0].
// 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.

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

conclusion

Who thinks it’s awesome? Throw this line of code at the interviewer when they ask you these questions!!

Of course, if you want to stay awesome, you need to read a lot of algorithm books, and I’ve compiled some of them

In this contribution to everyone, are some worth reading the algorithm book

You can get the download link of “I want to learn algorithm” from my wechat public account “Shuaidi Play programming”.

Tey, why don’t you leave without a thumbs up? mua

1, give me a thumbs up, can let more people see this article, by the way inspire me, hee hee.

2, old friends, follow my original wechat public account “Shuaidi Play Programming”, focusing on writing algorithm + basic knowledge of computer (computer network + operating system + database +Linux).

Save it so you can read it. Hit me. Background reply “ebooks” send you a selection of ebooks package, including a variety of skills of quality ebooks.

The author is simple

Author: Hello, everyone, MY name is Shuaidi. I have come all the way from university and college entrance exam. I know the importance of algorithm and basic knowledge of computer, so I applied for a micro-star public account “Shuaidi Play Programming”, specializing in writing these basic knowledge to improve our internal skills. Reprint description: Without authorization, reprint is prohibited