No. 14 - Last Number in a Circle

Problem: If we delete the m^th number from a circle which is composed of numbers 0, 1, …, n-1 counting from 0 at every time, what is the last number?

For example, a circle is composed of five numbers 0, 1, 2, 3, 4 as shown in Figure 1. If we delete the 3^rd number at every time, the deleted numbers are in order of 2, 0, 4, 1, so the last remaining number is 3.

Figure 1: A circle composed of 5 numbers 0, 1, 2, 3, 4.

Analysis: We are going to introduce two solutions for this problem here, one is classic and quite intuitive and the other is very creative.

Solution 1: Simulate a circle with a looped linked list

Because a circle is mentioned in the problem, an intuitive solution is to simulate a circle with some data structures. Looped linked can fulfill such a purpose. We may create a looped list with n nodes, and then delete the m^th node at every time from it.

We can implement the looped list based on the std::list in the C++ standard template library. It should be noticed that std::list itself is not looped. When an iterator reaches end of a list, we need to reset it to its head. It behaves like a circle with such a little trick. The sample source code of this solution is shown below:

int LastRemaining(unsigned int n, unsigned int m)

{

    if(n < 1 || m < 1)

        return -1;

    unsigned int i = 0;

    list<int> numbers;

    for(i = 0; i < n; ++ i)

        numbers.push_back(i);

    list<int>::iterator current = numbers.begin();

    while(numbers.size() > 1)

    {

        for(int i = 1; i < m; ++ i)

        {

            current ++;

            if(current == numbers.end())

                current = numbers.begin();

        }

        list<int>::iterator next = ++ current;

        if(next == numbers.end())

            next = numbers.begin();

        -- current;

        numbers.erase(current);

        current = next;

    }

    return *(current);

}

If we analyze the code above carefully, we can notice that a looped list is scanned for many times. Of cause, repeatedly scanning has negative impacts on time efficiency. In this solution, traversal with m steps are necessary to delete a node, so the time complexity is O(mn) for a looped list. Meanwhile, it requires a list with n nodes to simulate a circle, so the space complexity is O(n).

Solution 2: Analyze the pattern of deleted numbers

Firstly, let us define a function f(n, m), which stands for the last remaining number in a circle which has n numbers 0, 1, …, n-1 and the m^th number is deleted at each time.

The first deleted number in the circle is (m-1)%n, which is denoted as k for simplicity. The n-1 numbers after k is deleted are 0, 1, …, k-1, k+1, …, n-1. The last remaining number is also a function about n and m. The pattern of new sequence is different from the pattern of the original sequence, which begins with 0, so the function differs from the function f, which can be denoted as f’(n-1, m). The last remaining number of the original sequence should be the last remaining number of the sequence deleting k, so f(n, m)=f’(n-1, m).

Since we count the next m^th number from k+1, the sequence might be also viewed as k+1, …, n-1, 0, 1, …, k-1. We project this sequence of numbers into a new sequence in range of 0 and n-2:

k+1	→	0
k+2	→	1
…
n-1	→	n-k-2
0	→	n-k-1
1	→	n-k
…
k-1	→	n-2

If the projection is denoted as p, p(x)=(x-k-1%n, and the reversed projection is p^-1(x)=(x+k+1)%n.

The projected sequence has the same format as the original sequence because they both begin from 0. Therefore, its last remaining number is the projected sequence also follows rules of function f. We denoted as f(n-1, m).

The last remaining number of the sequence before projection is f’(n-1, m)= p^-1[f(n-1, m)]=[f(n-1, m)+k+1]%n. Since k=(m-1)%n, f(n, m)=f’(n-1,m)=[f(n-1, m)+m]%n.

A recursive equation is found after complex analysis. We can get last remaining number in a list with n numbers based on the last remaining number in a list with n-1 numbers. When n=1 (there is only one number 0 in the list), the last remaining number is obviously 0. The rules can be summarized as:

The equation can be implemented based on both recursion and iteration. The following code is based on iteration:

int LastRemaining(unsigned int n, unsigned int m)

{

    if(n < 1 || m < 1)

        return -1;

    int last = 0;

    for (int i = 2; i <= n; i ++)

        last = (last + m) % i;

    return last;

}

Even though the analysis is quite complex, its corresponding code is very simple. That is beauty of mathematics. More importantly, its time complexity is O(n) and space complexity is O(1), so it is much better than the first solution in both time and memory efficiency.

The discussion about this problem is included in my book <Coding Interviews: Questions, Analysis & Solutions>, with some revisions. You may find the details of this book on Amazon.com, or Apress.
 

The author Harry He owns all the rights of this post. If you are going to use part of or the whole of this ariticle in your blog or webpages,  please add a referenced to http://codercareer.blogspot.com/. If you are going to use it in your books, please contact me (zhedahht@gmail.com) . Thanks.