Removal of every 'kth' person from a circle. Find the last remaining person

Question

As part of a recent job application I was asked to code a solution to this problem.

Given,

• n = number of people standing in a circle.
• k = number of people to count over each time

Each person is given a unique (incrementing) id. Starting with the first person (the lowest id), they begin counting from 1 to k.

The person at k is then removed and the circle closes up. The next remaining person (following the eliminated person) resumes counting at 1. This process repeats until only one person is left, the winner.

The solution must provide:

• the id of each person in the order they are removed from the circle
• the id of the winner.

Performance constraints:

• Use as little memory as possible.
• Make the solution run as fast as possible.

I remembered doing something similar in my CS course from years ago but could not recall the details at the time of this test. I now realize it is a well known, classic problem with multiple solutions. (I will not mention it by name yet as some may just 'wikipedia' an answer).

I've already submitted my solution so I'm absolutely not looking for people to answer it for me. I will provide it a bit later once/if others have provided some answers.

My main goal for asking this question is to see how my solution compares to others given the requirements and constraints.

(Note the requirements carefully as I think they may invalidate some of the 'classic' solutions.)

Answer 1

Manuel Gonzalez noticed correctly that this is the general form of the famous Josephus problem.

If we are only interested in the survivor f(N,K) of a circle of size N and jumps of size K, then we can solve this with a very simple dynamic programming loop (In linear time and constant memory). Note that the ids start from 0:

int remaining(int n, int k) {
    int r = 0;
    for (int i = 2; i <= n; i++)
        r = (r + k) % i;

    return r;
}

It is based on the following recurrence relation:

f(N,K) = (f(N-1,K) + K) mod N

This relation can be explained by simulating the process of elimination, and after each elimination re-assigning new ids starting from 0. The old indices are the new ones with a circular shift of k positions. For a more detailed explanation of this formula, see http://blue.butler.edu/~phenders/InRoads/MathCounts8.pdf.

I know that the OP asks for all the indices of the eliminated items in their correct order. However, I believe that the above insight can be used for solving this as well.