# Josephus Problem Simulation

## Problem description

Josephus problem is a famous theoretical problem in mathematics and computer science. It describe such a situation:

There are N people standing in a circle waiting to be executed. Proccess beging at certain person in the circle, in each round, it skip the first M-1 person and the Mth person is killed, then the proccess continue from the next person. Obviously, one person is killed in each round, so after N-1 round, N-1 people get killed and the last person remains, who will be given freedom.

## Solution in python

we can simulate the josephus problem using dynamic array or circular linked list.

### Dynamic array

```def josephus_problem_with_dynamic_array(n, k):
index_arr = [i for i in range(1, n+1)]
person_pointer = 0
step_count = 1
while len(index_arr) > 1:
if step_count == k:
# remove the killed person from index arr
index_arr.pop(person_pointer)
person_pointer -= 1
person_pointer = (person_pointer + 1) % len(index_arr)
step_count = step_count % k + 1
return index_arr
```

### Circular linked list

```def josephus_problem_with_circular_linked_list(n, k):
class Node(object):
def __init__(self, index, next=None):
self.index = index
self.next = next
# initialize circular linked list
for i in range(2, n+1):
tmp = Node(i)
last_node.next = tmp
last_node = tmp
step_count = 1
while current_node.next != current_node:
if step_count == k:
# remove list node
current_node = current_node.next
last_node.next = current_node
else:
last_node = current_node
current_node = current_node.next
step_count = step_count % k + 1
return current_node.index
```
Current rating: 5