100 children join hands in a circle, counting from the first child to 3, the next child continues to count from 1, counting cycle, to find the position of the last child left in the queue.

This is a very classic algorithm question, and I often mention this question in interviews. This question is completely answerable through positive thinking, but unfortunately, in all the interviewees, almost no one can answer this question correctly.

So, how to solve this problem, let’s have a try!

Solution a: life and death see light, do not accept

First, we try to solve the problem with positive thinking. We simulate 100 people with a set whose values record the index (starting from 0) of the people in the original queue. In order to ensure the generality of the function, we use N to represent the number of people in the queue and M to represent the position of the queue:

This article is explained in Java language. If you want to see the implementation of other languages, please leave a message to me on the wechat official account “Ouyang Feng Studio”

Public static int f(int n, int m) {List<Integer> List = new ArrayList<>();for(int i = 0; i < n; i ++) { list.add(i); } // count = 0; Int index = 0;while(list.size() > 1) { count ++; If the count reaches the end of the queue, we need to count from the first person down // so the index counter here needs to return to 0if(index >= list.size()) { index = 0; } // Then start a loop to remove the person with the serial number m from the queueifList.remove (index); (count >= m) {list.remove(index); count = 0; } index ++; }return list.get(0);
}
Copy the code

The question is: Is this the right way to go?

Clearly not! This ignores the fact that the index of the queue changes as soon as someone is removed from the queue. For example, if the third person is removed, normally the next person should have an index of 4. In fact, this person’s index is still 3, because the index count is continuous. The index of the removed person will also disappear, and all subsequent people will be moved one place forward.

This was the most common problem with the above solution, and knowing the root of the problem, we continued to improve the code.

We add a line after line 28 of the above code to actively reduce the index value by one:

// Then start counting in a loop to remove the person with m from the queueifList.remove (index); (count >= m) {list.remove(index); count = 0; // index = 1; }Copy the code

After the modification, we try to run the above code, passing the values of 100 and 3 into the function, and get the result 90. The answer is correct.

Solution 2: death and life without fear, straight ahead

Direct to the solution of the problem, in addition to the above solution, there is a common solution, is no matter the three seven twenty-one, all the way round, until the output result.

This solution also requires building a user queue, but in a different form, we use a Boolean array of length N to build the user queue.

The complete code for this solution is as follows:

public static int f(int n, int m) {
    Boolean[] arr = new Boolean[n];
    for (int i = 0; i < arr.length; i ++) {
        arr[i] = true; } int leftCount = arr.length; Int count = 0; Int index = 0;while (leftCount > 1) {
        if (arr[index]) {
            count++;
        }

        if (count == m) {
            arr[index] = false; count = 0; leftCount --; } index ++; // We also need to handle the count reaching the end of the queueif (index >= n) {
            index = 0;
        }
    }

    int result = 0;
    for (int i = 0; i < arr.length; i ++) {
        if (arr[i]) {
            result = i;
            break; }}return result;
}
Copy the code

Compared with the first solution, this solution has a higher time complexity and more cycles, almost three to five times more cycles than the first solution, or even more. However, compared with the first method, this method is more acceptable and does not need to consider the change of index. In an interview, if you can’t think of any solution, I recommend using this solution.

Solution three: skillfully use linked list, scene restoration

Analyzing the questions, it is not difficult to find that this seems to be a very familiar linked list structure. In the third solution, we try to simulate the user queue using a linked list to see if it surprises us.

Since we always use one-way counting, we simulate this data structure with a one-way linked list:

Public class Child {public public Child next; public int value; public Child(int value) { this.value = value; }}Copy the code
public static int f(int n, int m) {
    Child head = new Child(0);

    Child current = head;
    for(int i = 1; i < n; i ++) { Child child = new Child(i); current.next = child; current = child; Next = head; // Next = head; // Next = head; Child prev = current; Child prev = current; current = current.next; Int count = 0; // Once the ends are connected, the current node points to itself, proving that there is only one user in the queuewhile(current.next ! = current) { count ++;if (count == m) {
            prev.next = current.next;
            count = 0;
        }

        prev = current;
        current = current.next;
    }

    return current.value;
}
Copy the code

This is the complete code for this solution, with a detailed explanation of each line of code. In this solution, we use linked list to simulate the queue of people, by controlling the current user’s pointer movement to simulate the count. Finally, the loop breaks out when the user’s next user pointer points to him, the game ends, and the current user is the last remaining user in the queue.

This solution is easier to understand than the above two solutions, and the time complexity of this solution is not high, and the number of cycles is the same as that of the first solution. So far, it’s the best solution of all.

So, is there a better solution?

Solution four: mathematical law, nine to one

Computer science can’t do without math! Finally, let’s give it a shot, and try to use the weapon of mathematics to solve this problem more subtly. Since this is a regular action, we can be sure that there should be a fixed mathematical law.

But now the question is, how do you find this pattern? That doesn’t seem easy.

So let’s assume that the total number of people in the queue is n, and the number of people in the queue is m, and we’ll use f(n, m) to represent the position of the people in the queue.

So just to make sense of it, let’s look at a real example, let’s say n=5, m=3, that there are only 5 people in the queue, and the person who counts 3 gets out.

In the first round of counting, the person in position 3 gets out of line [1, 2, X, 4, 5], and starts counting from 4. We move the person who starts counting to the first place, and the rest of the people move to the back in the order of counting, and a new queue is formed: [4, 5, 1, 2] From here, we start the second count, this time count position 1 out of the queue [4, 5, x, 2] we continue to follow the above way, switch queue, re-count for the third round: [2, 4, 5] => [2, 4, X] for the fourth round: [2, 4] => [x, 4]Copy the code

So that’s the complete count with n = 5 and m = 3, and we’re just going to focus on what happens on the first count.

After the first count, the queue changes from [1, 2, 3, 4, 5] to [4, 5, 2, 1].

  • Queue 1: [1, 2, 3, 4, 5]
  • Queue 2: [4, 5, 1, 2]

Notice, if we don’t care about the position of the person in the queue, we just care about the queue itself. What’s the relationship between these two queues?

  • Both queues count from 1
  • The two cohorts differ by only one

It’s kind of subtle here, but you can kind of view this as a queue of 5 characters, versus a queue of 4 characters. If we call the queue Q, the first queue can be called Q(5), the second queue can be called Q(4), and Q(4) is actually a subqueue of Q(5).

In these two queues, there are still two interference terms [1, 2]. In order to eliminate interference, we change them into [6, 7], namely:

  • Queue 1: [1, 2, 3, 4, 5]
  • Queue 2: [4, 5, 6, 7]

At this time, queue Q(5) has a certain relationship with Q(4), and the index value at the same position is exactly 3 different (in fact, it is the value of m, why m? Think about it for yourself).

Next, we focus on the first count of the second queue, and the person with the count of 3 gets out, which is 6 in queue 2. So, what was TA’s position in the original queue? And the answer is 1, which is essentially what you get by modulating 6 percent 5.

There seems to be a fixed rule here, that is, assuming that the position of the person in the first round of queue 2 is X2 in queue 2 and that of the person in queue 1 is X1, x2 and X1 should have the following relationship:

x1 = (x2 + 3) % 5
Copy the code

If the first count is true, is the second count true? Is it true all the way to the last person left? The answer is: yes, of course.

Thus, we can guess that f(n, m) and F (n, m-1) have the following relationship:

f(n, m) = (f(n - 1, m) + m) % n
Copy the code

In order to deepen your understanding, we will show you the conversion process with pictures once again:

The above is the process of converting n-1 others to n-1 subqueues after the user whose queue length is N and whose count is m for the first time steps out.

From this it can be concluded that the transformation here is universal and the above formula is applicable to all cases.

In the above formula, we do not consider the case that there is only one person in the current queue. Here, we complete it and get the following recursive formula:

f(n, m) = 0 (n = 1)
f(n, m) = (f(n - 1, m) + m) % n (n > 1)
Copy the code

With the above recursive formula, the problem becomes simple:

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

With the ternary operator, we can even solve this problem with one line of code:

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

Best practices

These are the common solutions to the “Joseph’s ring problem”. The most efficient solution is the fourth, followed by the first and third, and the second is the least efficient, but the easiest to think of. Although this problem can be solved most efficiently by mathematical induction, I still recommend the third solution, which is the one most suited to computer thinking. At the same time, the algorithm complexity is not high. But if you’re in a highly performance oriented program, of course, solution four is your best bet.

conclusion

In the process of solving this problem, we used linked lists, which are very common data structures. Maybe you use it a lot, but you don’t know it. Linked list problems often appear in algorithms, if you want to have a further understanding of linked lists, please pay attention to the public account “Ouyang Feng studio”, the next article we will talk about linked lists related to those algorithms.