CODEWITHSUNDEEP
c++algorithmlinked-list
Neel
Neel

Reputation: 141

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

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.

Upvotes: 3

Views: 350

Answers (6)

lenik
lenik

Reputation: 23556

This can easily be solved with O(1) complexity using the following:

last = (num - pow(2, int(log(num)/log(2)))) * 2 + 1

for example for num = 100 :

last = (100 - pow(2, int(log(100)/log(2)))) * 2 + 1 = 73

And if you have log2() function, you may replace a bit ugly log(num)/log(2) which basically takes a logarithm with the base 2.

Upvotes: 2

גלעד ברקן
גלעד ברקן

Reputation: 23945

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)

Upvotes: 3

Yunnosch
Yunnosch

Reputation: 26753

The method to reduce time complextiy is, as in most cases that a challenge fails for out-of-time reasons, to not simulate and use math instead. With luck it turns into a one-liner.

The algorithm can be sped up very much, if you change to:

Note that for a total number of prisoners which is a power of two, always index 0 will survive.

For other cases:

  • determine the highest power of two which is lower or equal to the number of prisoners
  • determine R, the rest when reducing the number of prisoners by that power of two
  • the prisoner who survives in the end will be the one who gets the knife after that number of prisoners has been killed

Trying to find out which prisoner that is.

Case of 5 prisoners (1 higher than 22, R=1):

         01234 
Deaths 1: x x
Deaths 2:x   x
last    :  O

Case of 6 (R=2):

         012345
Deaths 1: x x x 
Deaths 2:x x      (index 4 kills index 0 after index 2 was killed by index 0)
last    :    O

Case of 7 (R=3):

         0123456
Deaths 1:xx x x   (index 6 kills index 0 after index 5 was killed by index 2)
Deaths 2:  x x    (index 6 kills index 2 after index 4 was killed by index 2)
last    :      O

Case of 8 is the next power of two, index 0 survives.

In the end, the final survivor is always the one at index 2*R.
Hence, instead of simulating, you just need to determine R.
That should be possible at worst in a time complexity of order of logarithm to base 2 of total number.

Upvotes: 0

6502
6502

Reputation: 114579

For such a simple processing the list manipulation and memory allocation is going to dominate the computation, you could use just a single array where you have an index to the first alive and each element is the index of next alive.

That said you could indeed search for a formula that avoids doing the loops... for example if the number of prisoners is even then after the first "loop" you end up with half of the prisoners and the knife back in the hands of first one. This means that the index of the surviving prisoner when n is even is

f(n) = 2 * f(n / 2)   # when n is even

in case n is odd things are a bit more complex... after the first loop you will end up with (n + 1)/2 prisoners, but the knife in the hand of last one so some modulo arithmetic is needed because you need to "adjust" the result of the recursive call f((n + 1)/2).

Upvotes: 0

Has QUIT--Anony-Mousse
Has QUIT--Anony-Mousse

Reputation: 77485

The trick to reduce time complexity is to come up with more clever algorithms than brute-forcing it by simulation.

Here, as so often, key is obviously to solve the math. The first loop, for example, kills everybody with i%2=1 (assuming 0 based indexing), the second everybody with i%4=(n+1)%2*2 or so etc. - I'd be looking for a closed form to directly compute the survivor. It will likely boil down to a few bit manipulations yielding a O(log n) algorithm that is almost instant in practise because of all running completely in CPU registers with not even L1 cache accesses.

Upvotes: 0

Batman
Batman

Reputation: 702

Use 1 loop. You can grab, at every iteration, the current one's next, then set current to the next ones next and then delete the next one.

This assumes all the data is set up before hand and ignores the rewriting of the next variable when you hit the bounds.

Upvotes: 0

Related Questions