top button
Flag Notify
    Connect to us
      Site Registration

Site Registration

How to solve Josephus Problem using Linked List?

+5 votes
1,636 views

Josephus Problem talks about a problem where there are people standing in a circle waiting to be executed. The counting out begins at some point in the circle and proceeds around the circle in a fixed direction. In each step, a certain number of people are skipped and the next person is executed. The elimination proceeds around the circle (which is becoming smaller and smaller as the executed people are removed), until only the last person remains, who is given freedom.

posted Nov 23, 2013 by Mona Sharma

Share this question
Facebook Share Button Twitter Share Button LinkedIn Share Button

1 Answer

0 votes

Assume link list is circular link list, then have two functions like this and call eliminate with the index you want to skip after each execution.

public int RemoveAt(int index)
{
    int value = 0;
    Node current = first;
    do
    {
        if (current.Counter == index)
        {
            value = current.Data;
        }
        current = current.Next;
    } while (current != first);
    return value;
}

public int Eliminate(int m)
{
    int value = 0;
    Node current = first;
    Node nextNode;

    do
    {
        nextNode = current.next;
        value = RemoveAt(m);
        current = nextNode;

    } while (current != first);
    return value;
}
answer Nov 23, 2013 by Jai Prakash
Similar Questions
+2 votes

I am looking for sample code which can impress an interviewer.

+7 votes

Input:
First List: 5->6->3 // represents number 563
Second List: 8->4->2 // represents number 842
Output
Resultant list: 4->7->4->0->4->6 // represents number 474046

...