Josephus Special

Try First, Check Solution later

1. You should first read the question and watch the question video.
2. Think of a solution approach, then try and submit the question on editor tab.
3. We strongly advise you to watch the solution video for prescribed approach.

1. You are given an integer N which represents the total number of soldiers standing in a circle 
having position marked from 1 to N.
2. A cruel king wants to execute them but in a different way.
3. He starts executing soldiers from 1st position and proceeds around the circle in clockwise
direction.
4. In each step, every second soldier is executed.
5. The elimination proceeds around the circle (which is becoming smaller and smaller as the
executed soldiers are removed), until only the last soldier remains, who is given freedom.
6. You have to find the position of that lucky soldier.
Input Format
A number N
Output Format
Check the sample ouput and question video.
Question Video
Constraints
1 <= N <= 10^9
Sample Input
4
Sample Output
1


  • Editorial

    The problem here is based on a special case of the famous Josephus problem. We have already discussed the Josephus problem in our recursion section, here we will try to implement the special case of Josephus using bit manipulation.

    Let us try to understand the problem better with the help of an example. Here we have n = 6, and now we try to eliminate people alternatively:

    1. First Iteration - Numbers 2, 4, and 6 are eliminated. Hence we are left with 1, 3, and 5 for the next iteration. Another way to see this is that all numbers with 0th place having value 0 have been eliminated and hence the numbers with 0th index bit value 1 survives.

    2. Second Iteration - 3 gets eliminated or this time the number with 1st index as 1 gets eliminated, so the numbers with 1st index bit value as 0 survive. Now we have 1 and 5 left.

    3. Third Iteration - 1 gets eliminated or this time the number with 2nd index as 0 gets eliminated, so the numbers with 2nd index bit value as 1 survives. Now we have only number 5 remaining hence the answer.

    If we clealy observe then for

    N = 6

    N = 22 + 2 = 2x + L {where x is the highest power of 2 with 2x <= N}

    Answer = 2 * L  + 1 = 2 * 2 + 1 = 4 + 1 = 5 => [ 1 0 1 ]

    Now if we take a look at the survivors for every index we can notice that they are in the order [ 1 0 1 ] = 5.

    Hence this verifies our implementation with the formula.

    Now to understand the logic behind the formula:

    1. For the first iteration always all the numbers with the 0th index bit value as 0 will be eliminated hence always we would have the answer which would have the 0th index bit as 1. This explains having the (+1) term in the formula.

    2. Now say that for n = 6 the last number to be eliminated was 6 which has 0th index bit 0 this means in the next iteration all the numbers with 1st index bit value with 0 will survive as for the next iteration 1 will be saved and hence 3 will get eliminated.

    3. Now after the second iteration we have 1st index bit value for N (here 6) is 1 which implies that for the next iteration all elements with 2nd index bit value as 1 will survive.

    4. Hence after the third iteration, we are only left with 5 which has the value of 2 * L + 1 which is our resultant answer.

    Time Complexity: O(1)

    The time complexity for the function is constant.

    Space Complexity: O(1)

    The space complexity for the function is constant.

  • Asked in Companies
  • Related Topics






Video Solution

Code Solution

Run
 
Run
Id Name