Special Case of Josephus Problem: When K=2

Introduction

In this article, we will discuss a special case of Josephus problem, when k=2. But before that, we recommend you to visit the previous blog on ‘How to solve Josephus problem using Recursion and Linked List’. We discussed in detail the historical background of the problem and its standard problem statement.

It also explains the problem with the help of an example and talks about the various approaches to find a general solution to it. 

Problem Statement of Josephus Problem’s Special Case

Before diving into the special case, let’s go through the problem statement first. The general problem statement for Josephus problem is as follows-

N people are standing in a circle waiting to get executed, and counting starts from a certain point in the circle, in a specific direction, either clockwise or counterclockwise. After skipping k people, the next person gets executed. The exact process is repeated for the remaining people, starting with the next person from the last executed person. We again skip k people to execute the next person. We do this until only one person is left. We need to find the person’s position of who survives in the initial circle with n people.

The special case occurs when k=2. We can reframe the problem as follows-

We have n numbers arranged in a circle. Starting from 1, we start deleting every second number and find the last number that gets deleted.

Explanation of the Special Case of Josephus Problem

We can understand this case with the help of the following example when n=6. So, we arrange numbers up to 6 in a circle and delete every second number while moving clockwise in the circle-

• We start with the number marked as 1 and delete the second number, i.e., 2. Now the next second number is 4, so we delete it, and the next second number is 6, so we delete it as well. Thus after one circle, we have been left with 1, 3, 5, and 1 as the starting position.
• Now we start with 1 and find that 3 is the second number to be deleted. After this round, we have 1 and 5, and 5 as starting positions.
• Now we start with 5 and delete the second number, i.e., 1. Thus we are left with 5 as the last number to be deleted.

From the above example, we can make few conclusions as well-

In the first round of the circle, we delete all the even numbers.

For further cases- If a number is at position x in the current round. It was at the 2x-1th position in the previous round, if n is even. Or, it was at 2x+1th position in the last round if n is odd.

Let’s dive into finding the solution to this special case of Josephus’ problem. We will start with the method using recurrence relation, and then we move to a method that uses left rotation to find the solution.

The Method using Recurrence Relation

This method first finds the recurrence relation for the position of the number, which will be the last one to be deleted. To find this recurrence relation, we use the observations we made in the above explanation that for even values of n, the number at position x in the current round was at position 2x-1 in the previous round. If n is odd, then the number at the position x in the current round was at 2x+1 position in the previous round. 

Thus we can frame the recurrence relation as follows-

If T(n) is the position of the number to be deleted last in the initial round-

T(n) = T*f(n/2) – 1, for even values of n.

T(n) = 2*T((n-1)/2) + 1, for odd values of n.

On solving the above recurrence relation we find the solution to be-

T(n) = 2*n – 21+ floor(Log2n)+ 1.

The above equation might look complex, but it simply means that for a given n, find the power of 2 just greater than n. Let’s say it is Q. Then the number that gets deleted last is 2*n-Q+1. You can check that for the example we discussed above for n=6. The number deleted in the last is 5. Using this method, Q is 8, making 2*n-Q+1=12-8+1=5, which is the correct answer. 

Algorithm

• Take n as input from the user.
• Call the Josephus function with n as an argument.
• Josephus’ function finds Q, the power of 2 just greater than n.
• Josephus function then returns 2*n-Q+1.

Implementation for Approach using Recurrence Relation

#include <bits/stdc++.h>
using namespace std;
//Function to fint the number to be deleted last
//it takes n as the argument.
int Josephus(int n)
{
    //Declaring a variable to find the power of 2 ///just larger than n.
    int Q=1;
    while(Q<=n)
    {
        Q*=2;
    }
    //Returning the number to be deleted last.
    return (2*n)-Q+1;
}
//Driver function.
int main()
{
    int n;
    cout<<"Enter n "<<endl;
    //taking n from the user input.
    cin>>n;
    //Printing the last number to be deleted.
    cout<<" The last number to be deleted is "<<Josephus(n)<<endl;
    return 0;
}

Input-

6

Output-

Enter n 
The last number to be deleted is 5

The time complexity of this approach is O(logN).

The space complexity of this approach is O(1).

Method using Corollary

In mathematics, we call a statement a corollary if it is the natural and direct result. This special case of the Josephus problem also has a corollary as a concept which we use to solve it. This corollary states that if we left to rotate the binary representation of the n, the number represented after the rotation is the number that will be deleted last from the circle. It also dictates that for every number which is a power of 2, the last number to be deleted is always 1.

Algorithm

• Take n from user input.
• Call the Josephus function, which takes n as the argument.
• This function then checks if n is a power of 2, if yes the last number to be deleted will be 1 per the corollary.
• It then changes the n into the binary number of 32 bits.
• Then we search for the leftmost set bit.
• Then the array’s values are rotated to their left by one position 1
• Then convert the binary number into an integer and return it.

Implementation of Approach using Corollary

#include <bits/stdc++.h>
using namespace std;
//Function to fint the number to be deleted last
//it takes n as the argument.
int Josephus(int n)
{
    //Checking for the corrolary about the numbers //as power of 2.
    if (!(n & (n - 1)) && n) 
    {
        return 1;
    }
    bitset<32> binaryn(n);
    //To find the left most set bit.
    bool flag = false;
    for (int i=31;i>=0;i--) 
    {
        if(binaryn[i]==1&&!flag) {
            flag = true;
            binaryn[i]=binaryn[i - 1];
        }
        //To shift bits.
        if(flag)
        {
            binaryn[i] = binaryn[i - 1];
        }
    }
    binaryn[0] = 1;
    int lastnum;
    //To get the number back in int.
    lastnum= (int)(binaryn.to_ulong());
    return lastnum;
 
}
//Driver function.
int main()
{
    int n;
    cout<<"Enter n "<<endl;
    //taking n from the user input.
    cin>>n    //Printing the last number to be deleted.
    cout<<" The last number to be deleted is "<<Josephus(n)<<endl;
    return 0;
}

Input-

6

Output-

Enter n 
 The last number to be deleted is 5

The time complexity of this approach is O(logN).

The space complexity of this approach is O(logN).

Frequently Asked Questions

Key takeaways

In this article, we discussed the special case of Josephus problem, when k=2 and how we can solve it-

• The first method was to find a recurrence relation among the position of a number in the circle in different rounds. Then we solved the recurrence relation to concluding that for a given n, the number to be deleted last is (2*n)-Q+1, where Q is the power of 2 just above n.
• The second method uses a corollary that states that if we left to rotate the binary representation of n, we get the number to be deleted last in the circle. Also, if n is a power of 2, the number to be deleted last is 1.

You can read more about recurrence relations here. Solve problems related to these on CodeStudio. If you liked this blog, share it with your friends!

Check out this article on the general Josephus problem and its solutions.

By: Gorakhnath Yadav