Last Updated: 2 Mar, 2021
Josephus
Moderate
Asked in companies
‘N’ people are standing in a circle numbered from ‘1’ to ‘N’ in clockwise order. First, the person numbered 1 will proceed in a clockwise direction and will skip K-1 persons including itself and will kill a Kth person. Now (K+1)th person from 1 will start and will kill the Kth person from itself.
You have to find the position of the last person surviving with respect to initial numbering.
Note:
A person can also kill himself.
Input Format
The first line of input contains an integer ‘T’ denoting the number of test cases.
The first and only line of each test case contains two integers ‘N’ and ‘K’. Where ‘N’ is the total no of persons standing around circle and ‘K’ number indicates kth person is killed.
Output Format
For each test case, return a single integer denoting the position of the last person surviving.
Note:
You are not required to print the output explicitly, it has already been taken care of. Just implement the function.
Constraints
1 <= ’T’ <= 50
1 <= ’N’,’K’ <= 10^4
Time Limit: 1 sec
Approaches
Approach:- The key id is to store all positions of a person in vector and remove all kth position from starting point in vector. After removing an element from the vector starting point is also changed.
Algorithm:
- Store all the positions of persons in the index array.
- Initially the starting position will be 0(since pos[0]=1).
- Delete the element at position 'START1'= (START + K - 1) % N. Whereas ‘N’ is the size of the index array.
- Now the starting position will be ‘START1’.
- Repeat step3 until size of array becomes equal to 1.
- Return the only element of index array.
The key idea is find the answer for ‘N’ persons around the circle first find the answer for 'N-1' persons. First kill the Kth person from 1st position then recursively call on 'N-1'. It will give the position but according to with Kth person index set as 1. So to set the index will add ‘K’ to the index and will do mod ‘N’. If it comes out to be 0 then the value of index is ‘N’.
Algorithm:-
- Consider the base case when ‘N’ == 1 so answer will be 1.
- Recursively call on ‘N-1’ persons.It will give the position for ‘N-1’ persons .
- The answer from recursion is position but according to the Kth person.So to covert, it into the original position add ‘K’ to it and do ‘N’ mod with it(If the value exceeds n so it has come back to starting positions). If it is equal to 0 then the index will be ‘N’.
- Return the index
Similar problems