Josephus Problem

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.

K Number

Examples:

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

Confused about your next job?

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



Expand in New Tab 

 

Explanation:

output 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:

Recursive Approach

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.

using list

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[0] << 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[0])
        return
 
    index = (index + k) % len(person)
    person.pop(index)
    Josh(person, k, index)
 
 
def solve(N, K):
 
    K = K - 1
    index = 0
 
    persons = [0] * (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

NGINX vs Apache: What’s The Difference?

Next Post
Happy Number

Happy Number

Total
0
Share