In n circle size removing k th person every time until 1 remains

Question

In one site there was one practice question which ask you to make one program:

Tapas and Meghana are appointed as the one responsible for interviews of AXIS Core committee '17 ! In order to decide upon the order in which to call the aspirants for the interview, they have come up with a brilliant game. It goes like: the core game is divided into \$N\$ phases; and \$N\$ aspirants, successively numbered from \$1\$ to \$N\$, are moving round a circle one after another, i.e. the first follows the second, the second follows the third, ..., the \$(N-1)\$th follows the \$N\$th, and the \$N\$th follows the first. At each phase, a single aspirant is made to leave the circle and is taken up for interview. While the others continue to move. At some phase, the circle is left by an aspirant, who is marching \$K\$ positions before the one, who left the circle at the previous phase. An aspirant, whose number is \$K\$, leaves the circle at the first phase.

Input The only line contains the integer numbers \$N\$, and \$K\$.

Output You should output the order in which in the aspirants give their interviews. The numbers should be separated by single spaces.

Constraints \$1\le N\le 100000\$; \$1\le K\le N\$.

According to my understanding this question is related to queue.

My program:

a,b = raw_input().split()
a = int(a)
b = int(b)
c = []
d = []
for i in range(a, 0, -1):
    c.append(i)
while len(c) != 0:
    for i in range(1, b):
        f = c.pop()
        c.insert(0, f)
    print c.pop(),

This code was working fine but on some input cases it was showing time limit exceed. So I was wondering that if there is any algorithm which can work better than this or is there any problem with my code which I don't know ?

Answer 1

1. Review

1. If all the code is at the top level of the module, and reads from standard input, it is hard to test it or measure its performance. It's better to organize the code into functions so that they can be easily tested.

2. The values in the problem have the names \$N\$ and \$K\$ but in the code they have the names a and b. This makes it hard to check the code against the problem. It would be better to be consistent.

3. The code initializes the list c by repeatedly calling its append method:

   c = []
   for i in range(a, 0, -1):
       c.append(i)
   

   Instead, just call list:

   c = list(range(a, 0, -1))
   

4. The variable d is not used and could be omitted.

5. Instead of testing len(c) != 0, just test c.

6. The loop index i is not used; it's conventional to name an unused variable _.

7. Instead of:

   f = c.pop()
   c.insert(0, f)
   

   you could save a line and write:

   c.insert(0, c.pop())       
   

2. Revised code

def josephus(n, k):
    """Yield the order in which people are removed from the circle in the
    Josephus problem starting with n people and removing every k'th
    person.

    """
    c = list(range(n, 0, -1))
    while c:
        for _ in range(1, k):
            c.insert(0, c.pop())
        yield c.pop()

def main():
    n, k = map(int, raw_input().split())
    print(' '.join(josephus()))

3. Performance analysis

The while c: loop executes \$N\$ times, each for loop executes \$K-1\$ times, and inserting an item at the start of a list takes time proportional to the length of the list (see the time complexity page on the Python wiki). So the overall runtime is \$Θ(N^2K)\$.

4. Performance improvement

We can avoid one of the factors of \$N\$ in the runtime by using a collections.deque instead of a list and calling the rotate method:

from collections import deque

def josephus(n, k):
    """Yield the order in which people are removed from the circle in the
    Josephus problem starting with n people and removing every k'th
    person.

    """
    c = deque(range(n, 0, -1))
    while c:
        c.rotate(k - 1)
        yield c.pop()

This brings the runtime down to \$Θ(NK)\$ which might be acceptable, but since you didn't give us the link, I can't check whether that's the case.