-->

9/23/20

Josephus problem Solution with code and explanation

Josephus problem Solution-

Read Josephus Story -here



Problem Statement

Given the total number of persons n and a number k which indicates that k-1 persons are skipped and kth person is killed in circle in a fixed direction.​
The task is to choose the safe place in the circle so that when you perform these operations starting from 1
st place in the circle, you are the last one remaining and survive.



Example 1:

Input:
n = 3 k = 2
Output: 3
Explanation: There are 3 persons so 
skipping 1 person i.e 1st person 2nd 
person will be killed. Thus the safe 
position is 3

Josephus problem Solution -
Josephus servived  because he knew maths and recursion that's why he stand at 40th place.
I also know recursion so I can also survive when I will face a similar problem So you should also know How to survive in such situation for that you also have to learn recursion.
😆😆😆XD
 i have to think how can i break 
this problem into subproblem 
People are standing in a circle so counting form very first place 
i have to delete every k-1 th node from current index
For example, if n = 5 and k = 2, then the safe position is 3. Firstly, 
the person at position 2 is killed, then person at position 4 is killed,
 then person at position 1 is killed. Finally, the person at position 5
 is killed. So the person at position 3 survives.
If n = 7 and k = 3, then the safe position is 4. The persons at positions 3, 6, 2, 7, 5, 1 are
 killed in order, and person at position 4 survives.

i have simple approach i will first add all person in a vector and delete i will kill every k-1 th person and start countin again from new position
Now think about the smallest problem 
when I have only one person in my vector this will my solution no matter what is the value of k 
so let's write base case 

if(v.size()==0){
return v[0];
}

Now Think about induction step
If i am standing in a generic position in my vactor what will my intension 
to delete kth node from my posion if it is out of box start count from begin .
so i will find next index which i have to delete and then i will call my solve funcion which will return 
me final ans
induction step 
index=(index+k)%v.size();
v.erase(v.begin()+index);
return solve(v,index,k,ans);


final code is here- must share with your friends  



Advertiser

all right reserved @technicalkeeda.in. Powered by Blogger.