# Josephus Problem

## Problem Statement

There are N people standing in a circle numbered from 1 to N. Also given an integer K. First, count the K-th number starting from the first one and delete it. Then K numbers are counted starting from the next one and the K-th one is removed again, and so on. The process stops when one number remains. The task is to find the last number.

Examples:

Input: N = 6, K = 2
Output: 5

In 3 simple steps you can find your personalised career roadmap in Software development for FREE

Explanation:

## Recursive Approach

A simple approach to solve this problem is to find the position of the step which would be called after each execution.

Therefore, given N persons, and skipping K persons during their deletion, N – 1 persons will be left. Therefore, we need to call the recursive function for N – 1 and K for the next iteration.

Now, for each remaining circle after execution, we need to find the last remaining person present i.e. if Kth person is executed, K+1th will be the next starting safe point the recursive call. Therefore, to keep a track of the position, perform K%N + 1.

The recursive function would be:

josephus(N, K) = (josephus(N – 1 , K) + K – 1) % N + 1.

You can also observe a pattern as follows:

Algorithm

• If N  == 1, return 1. This is the termination condition for the function.
• Else, return (josephus(N – 1 , K) + K – 1) % N + 1.

### C++ Code For Recursive Method

```int josephus(int N, int K) {
if (N == 1)
return 1;
else
return (josephus(N - 1, K) + K - 1) % N + 1;
}```

### Java Code For Recursive Method

``` static int josephus(int N, int K) {
if (N == 1)
return 1;
else
return (josephus(N - 1, K) + K - 1) % N + 1;
}```

### Python Code For Recursive Method

```def josephus(N, K):

if N == 1:
return 1
else:
return (josephus(N - 1, K) + K - 1) % N + 1```

Time Complexity: O(N)
Space Complexity: O(N), depth of the recursion tree.

## Using List – Approach 2

In this approach, initialize a list containing all integers from 1 to N and delete every Kth node until one element is left.

Algorithm

• Create a list containing integers from 1 to N.
• Create a recursive function which deletes every Kth element from the list in each iteration in the clockwise direction.
• Continue repeating the above steps until only one element is left.

Implementation of the Approach:

### C++ Implementation

```void Josh(vector < int > person, int k, int index) {
if (person.size() == 1) {
cout << person << endl;
return;
}
index = ((index + k) % person.size());
person.erase(person.begin() + index);
Josh(person, k, index);
}

solve(n, k) {
k--;
int index = 0;

vector < int > person;
for (int i = 1; i <= n; i++) {
person.push_back(i);
}

Josh(person, k, index);
}```

### Java Implementation

``` static void Josh(ArrayList < Integer > person, int k, int index) {
if (person.size == 1) {
System.out.println(person.get(0));
return;
}
index = ((index + k) % person.size());
person.remove(index);
Josh(person, k, index);
}

solve(int N, int K) {
K = K - 1;
int index = 0;

Arraylist < Integer > person;
for (int i = 1; i <= N; i++) {
person.push_back(i);
}

Josh(person, K, index);
}```

### Python Implementation

```def Josh(person, k, index):
if len(person) == 1:
print(person)
return

index = (index + k) % len(person)
person.pop(index)
Josh(person, k, index)

def solve(N, K):

K = K - 1
index = 0

persons =  * (N)
for i in range(1, N + 1):
person.append(i)

Josh(person, K, index)```

Time Complexity: O(N), where N is total persons.
Space Complexity: O(N), a list of size N, is used.

## Special Case: K = 2

For K = 2, the problem becomes much easier to solve.

In case, N is even, first all even positions will get deleted. Then, the remaining N / 2 remains. Therefore, the answer for the remaining N can be found from the answer for N / 2 by multiplying it with 2 and subtracting 1 i.e. shifting the positions.

The answer for even N can obtained as –

josephus(2 * N, 2) =  josephus(N, 2) – 1

Similarly, In case, N is odd, first, all even positions will get deleted. Then, remaining (N – 1) / 2 remains. Therefore, the answer for the remaining N can be found from the answer for (N – 1) / 2 by multiplying it with 2 and subtracting 1 i.e. shifting the positions.

The answer for even N can obtained as –

josephus(2 * N + 1, 2) =  josephus(N, 2) – 1

From the above relations, both can be merged and can be written as –

josephus(N, 2) = 1 + 2 * (N – 2 ^(floor(log2(N))

### C++ Code

```int josephus(int N) {
int p = 1;
while (p <= N)
p *= 2;

return (2 * N) - p + 1;
}```

### Java Code

``` static int josephus(int N) {
int p = 1;
while (p <= N)
p *= 2;

return (2 * N) - p + 1;
}```

### Python Code

```def josephus(N):
p = 1
while p <= N:
p *= 2

return (2 * N) - p + 1```

Time Complexity: O(logN), where N is total steps.
Space Complexity: O(1), as no extra s[ace is used.

## Practice Question

100 People In A Circle

## FAQs

What data structure is used in solving the Josephus problem?
A list can be used to solve the Josephus problem, which initially contains all the integers from 1 to N.

How to solve the Josephus problem?
The Josephus problem can be solved using recursion. For each iteration, recursively delete the Kth position until only one person is left.

##### Previous Post ## NGINX vs Apache: What’s The Difference?

##### Next Post 