Redirecting to
NADOS

Josephus Problem

  Prev   Next

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 two numbers N and K.
2. N represents the total number of soldiers standing in a circle having position marked from 0 to N-1.
3. A cruel king wants to execute them but in a different way.
4. He starts executing soldiers from 0th position and proceeds around the circle in clockwise direction.
5. In each step, k-1 soldiers are skipped and the k-th soldier is executed.
6. 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.
7. You have to find the position of that lucky soldier.

Note -> Check out the question video and write the recursive code as it is intended without  changing signature. The judge can't force you but intends you to teach a concept.
Input Format 
2 numbers N and K
Output Format 
Check the sample ouput and question video.
Question Video
Constraints 
1 <= N,K <= 200
Sample Input 
4
2
Sample Output 
0


  • Editorial

    After killing the first soldier, we will append the first k - 1 soldiers to the end. Because of the circular effect, there is nothing wrong with this.

    Example -

    N = 5 , K = 3

    0 1 2 3 4

    After executing 3, our soldiers will be arranged like this.

    3 4 0 1 ----------------------------(y)

    Initially the problem was for 5 soldiers, now it is for 4 soldiers. Let us transform the remaining soldiers such that 3 will now be 0, 4 will be 1 , 0 will be 2 and 1 will be 3. We will later find the relation between (y) and (x).

    0 1 2 3 ---------------------------- (x)

    Now after executing the Kth soldier ,

    0 1 2                                                                                                                                      3

    3 0 1 ---------------(y)

                                                                                                                                                    /

    Again we will transform the remaining soldiers,                                                         |

                                                                                                                                                     /

                                                                                                                                                  0 1 2  ---------------(x)         

    Now executing the kth soldier again and transforming till only one soldier is left,     

    0 1 2  0 1

               /

                |

               /

               0 1

                  /

                   |

                  /

                  0

    The relation between (y) and (x) is -

    y  = (x + k) % n ---------------------- (1)

    Where n is the remaining soldiers at the y level. We see that n reduces at every level but k remains constant.

    After executing the kth soldier at nth level, we keep faith that recursion will return us the answer for n-1 soldiers. To meet our expectation, we will convert the ans returned to us from the recursion by using the equation (1).

    When only one soldier is left, 0 will be the answer, so we will return 0(BASE CASE).

    Recursion Tree -

    Code -

    public static int solution(int n, int k){
                                    if(n == 1){ // base case
                                      return 0;
                                    }else{
                                      int x =  (solution(n - 1, k); // faith
                                      int y = (x + k) % n; // meeting our expectation	
                                    }
                                }

    java false

    Code Explained -

    When n is not equal to 1, then we will keep faith that recursion will return us the answer for n-1 soldiers.

    We will find answer for n-1 soldiers (x)

    Then to meet our expectation we will convert (x) to (y) with the help of equation (1).

    Base Case -

    When n is equal to 1, then we have to return 0 as only one soldier survives and that is the answer.

    Time Complexity - O(n)

    We call recursive function n times. Therefore, the time complexity will be equal to O(n).

    Space Complexity - O(n)

    As we call recursive function n times, therefore the recursion stack will be filled n times . Therefore, the space complexity will be O(n).

  • Asked in Companies
  • Related Topics






Video Solution

Code Solution

Run
 
Run
Id Name