Removal of every 'kth' person from a circl

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

This is my solution, coded in C#. What could be improved?

public class Person
{
    public Person(int n)
    {
        Number = n;
    }

    public int Number { get; private set; }
}


static void Main(string[] args)
{
    int n = 10; int k = 4;
    var circle = new List<Person>();

    for (int i = 1; i <= n; i++)
    {
        circle.Add(new Person(i));
    }

    var index = 0;
    while (circle.Count > 1)
    {
        index = (index + k - 1) % circle.Count;
        var person = circle[index];
        circle.RemoveAt(index);
        Console.WriteLine("Removed {0}", person.Number);
    }
    Console.ReadLine();
}
        Console.WriteLine("Winner is {0}", circle[0].Number);

Answer 2

Here is a solution in Clojure:

(ns kthperson.core
  (:use clojure.set))


(defn get-winner-and-losers [number-of-people hops]
  (loop [people (range 1 (inc number-of-people))
         losers []
         last-scan-start-index (dec hops)]
    (if (= 1 (count people))
      {:winner (first people) :losers losers}
      (let [people-to-filter (subvec (vec people) last-scan-start-index)
            additional-losers (take-nth hops people-to-filter)
            remaining-people (difference (set people)
                                         (set additional-losers))
            new-losers (concat losers additional-losers)
            index-of-last-removed-person (* hops (count additional-losers))]
        (recur remaining-people
               new-losers
               (mod last-scan-start-index (count people-to-filter)))))))

Explanation:

• start a loop, with a collection of people 1..n

• if there is only one person left, they are the winner and we return their ID, as well as the IDs of the losers (in order of them losing)

• we calculate additional losers in each loop/recur by grabbing every N people in the remaining list of potential winners

• a new, shorter list of potential winners is determined by removing the additional losers from the previously-calculated potential winners.

• rinse & repeat (using modulus to determine where in the list of remaining people to start counting the next time round)