Is there a way to reduce the time complexity of the program?

Question

Assume there are n prisoners standing in a circle. The first prisoner has a knife with which he kills the second prisoner and passes on the knife to the third person who kills the fourth prisoner and passes the knife to the fifth prisoner.

This cycle is repeated till only one prisoner is left. Note that the prisoners are standing in a circle, thus the first prisoner is next to the nth prisoner. Return the index of the last standing prisoner.

I tried implementing the solution using a circular linked list. Here's my code

The structure of the circular linked list is:-

struct Node
{
    int Data;
    Node *Next;
};
Node *Head = NULL;

Here are my deleteByAddress() and main() functions:-

inline void deleteByAddress(Node *delNode)
{
Node *n = Head;
if(Head == delNode)
{
    while(n -> Next != Head)
    {
        n = n -> Next;
    }
    n -> Next = Head -> Next;
    free(Head);
    Head = n -> Next;
    return ;
}

while(n -> Next != delNode)
{
    n = n -> Next;
}
n -> Next = delNode -> Next;
delete delNode;
}

int main(void)
{
for(int i = 1 ; i <= 100 ; i++)
  insertAtEnd(i);

Node *n = Head;
while(Head -> Next != Head)
{
    deleteByAddress(n -> Next);
    n = n -> Next;
}
cout << Head -> Data;
return 0;
}

The above code works perfectly and produces the desired output for n = 100, which is 73.

Is there any way we can reduce the time complexity or use a more efficient data structure to implement the same question.

Answer 1

This is known as the Josephus problem. As the Wikipedia page shows and others have noted, there is a formula for when k is 2. The general recurrence is

// zero-based Josephus
function g(n, k){
  if (n == 1)
    return 0
  
  return (g(n - 1, k) + k) % n
}

console.log(g(100, 2) + 1)