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

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 i开发者_Go百科t 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.)

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.

You can do it using a boolean array.

Here is a pseudo code:

Let alive be a boolean array of size N. If alive[i] is true then ith person is alive else dead. Initially it is true for every 1>=i<=N
Let numAlive be the number of persons alive. So numAlive = N at start.

i = 1 # Counting starts from 1st person.
count = 0;

# keep looping till we've more than 1 persons.
while numAlive > 1 do

 if alive[i]
  count++
 end-if

 # time to kill ?
 if count == K
   print Person i killed
   numAlive --
   alive[i] = false
   count = 0
 end-if

 i = (i%N)+1 # Counting starts from next person.

end-while

# Find the only alive person who is the winner.
while alive[i] != true do
 i = (i%N)+1
end-while
print Person i is the winner

The above solution is space efficient but not time efficient as the dead persons are being checked.

To make it more efficient time wise you can make use of a circular linked list. Every time you kill a person you delete a node from the list. You continue till a single node is left in the list.

The problem of determining the 'kth' person is called the Josephus Problem. Armin Shams-Baragh from Ferdowsi University of Mashhad published some formulas for the Josephus Problem and the extended version of it. The paper is available at: http://www.cs.man.ac.uk/~shamsbaa/Josephus.pdf

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);

Essentially the same as Ash's answer, but with a custom linked list:

using System;
using System.Linq;

namespace Circle
{
    class Program
    {
        static void Main(string[] args)
        {
            Circle(20, 3);
        }

        static void Circle(int k, int n)
        {
            // circle is a linked list representing the circle.
            // Each element contains the index of the next member
            // of the circle.
            int[] circle = Enumerable.Range(1, k).ToArray();
            circle[k - 1] = 0;  // Member 0 follows member k-1

            int prev = -1;  // Used for tracking the previous member so we can delete a member from the list
            int curr = 0;  // The member we're currently inspecting
            for (int i = 0; i < k; i++)  // There are k members to remove from the circle
            {
                // Skip over n members
                for (int j = 0; j < n; j++)
                {
                    prev = curr;
                    curr = circle[curr];
                }

                Console.WriteLine(curr);
                circle[prev] = circle[curr];  // Delete the nth member
                curr = prev;  // Start counting again from the previous member
            }
        }
    }
}

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)

This is a variant of the Josephus problem.

General solutions are described here.

Solutions in Perl, Ruby, and Python are provided here. A simple solution in C using a circular doubly-linked list to represent the ring of people is provided below. None of these solutions identify each person's position as they are removed, however.

#include <stdio.h>
#include <stdlib.h>

/* remove every k-th soldier from a circle of n */
#define n 40
#define k 3

struct man {
    int pos;
    struct man *next;
    struct man *prev;
};

int main(int argc, char *argv[])
{
    /* initialize the circle of n soldiers */
    struct man *head = (struct man *) malloc(sizeof(struct man));
    struct man *curr;
    int i;
    curr = head;
    for (i = 1; i < n; ++i) {
        curr->pos = i;
        curr->next = (struct man *) malloc(sizeof(struct man));
        curr->next->prev = curr;
        curr = curr->next;
    }
    curr->pos = n;
    curr->next = head;
    curr->next->prev = curr;

    /* remove every k-th */
    while (curr->next != curr) {
        for (i = 0; i < k; ++i) {
            curr = curr->next;
        }
        curr->prev->next = curr->next;
        curr->next->prev = curr->prev;
    }

    /* announce last person standing */
    printf("Last person standing: #%d.\n", curr->pos);
    return 0;
}

Here's my answer in C#, as submitted. Feel free to criticize, laugh at, ridicule etc ;)

public static IEnumerable<int> Move(int n, int k)
{
    // Use an Iterator block to 'yield return' one item at a time.  

    int children = n;
    int childrenToSkip = k - 1;

    LinkedList<int> linkedList = new LinkedList<int>();

    // Set up the linked list with children IDs
    for (int i = 0; i < children; i++)
    {
        linkedList.AddLast(i);
    }

    LinkedListNode<int> currentNode = linkedList.First;

    while (true)
    {
        // Skip over children by traversing forward 
        for (int skipped = 0; skipped < childrenToSkip; skipped++)
        {
            currentNode = currentNode.Next;
            if (currentNode == null) currentNode = linkedList.First;
        }

        // Store the next node of the node to be removed.
        LinkedListNode<int> nextNode = currentNode.Next;

        // Return ID of the removed child to caller 
        yield return currentNode.Value;

        linkedList.Remove(currentNode);

        // Start again from the next node
        currentNode = nextNode;
        if (currentNode== null) currentNode = linkedList.First;

        // Only one node left, the winner
        if (linkedList.Count == 1) break;  
    }

    // Finally return the ID of the winner
    yield return currentNode.Value;
}