Lucky Alive Person in a Circle
This problem is based on one of the most famous puzzles, The Josephus Problem. Here we will be finding the luckiest person to be alive among other soldiers.
We will try to solve this in the best time and space complexity.
Let's understand the problem statement. We are given a circle having n people standing in it. The first soldier has the sword, and that soldier kills the next person. The sword will be handed over to the third soldier as soon as the first soldier kills the next soldier. Now, this third soldier kills the next soldier, and this process keeps going. As a result, we have to find the luckiest person who is still alive.
Let me make you understand with a quick example.
|Input: N = 4|
Initially, 1 has the sword, '1' will kill its next member which is 2, and give its sword to 3. Now '3' will kill its next member, '4' and hand over the sword to 1. '1' will kill its next member, which is now 3 . So 1 is the only luckiest person alive.
A pictorial view of this example will give you more clarity.
Now let's see how we can build our logic for this particular problem. While finding the luckiest soldier for every variant of n, we find a specific pattern.
Let me make you clear about the pattern through the table below.
Number of soldiers(n)
- Now, as you can see the pattern here, the luckiest person is always the odd one. Can you tell me why the luckiest person is always the odd value? The answer to this is for any value of 'n' even value will be killed in the first round itself as we are starting from '1' and every soldier is killing its adjacent soldier.
- The second pattern which you can notice is that the power of '2' has the luckiest person as '1'. If n= 2^x, then the problem will recursively reduce to (2^x)-1.
- The third pattern which you can observe is that other than the luckiest person of n = 2^x, all are increasing by 2. For '9', it will be 3; for '10', it will be 5; for 11, it will be 7; for 12, it will be 9, and so on till 2^x where the luckiest number will again be 1.
Every number can be represented in the form of 2.
10 = 2^3 + 2^1
12 = 2^3 + 2^2 and so on...
So for every number, we can represent n = 2^x + l
Here 'l' will be the number of steps to reach the luckiest person.
Suppose n= 10. '10' can be represented as 8+2. Here will be taking two steps (l=2) and find the answer.
We can verify this also with the help of an image:
So yaa '5' is the right answer.
This is the most efficient approach to solve this problem. The time complexity to solve this problem is O(1).
Space complexity is O(1) as no extra space is required by the bits.
Frequently Asked Questions
- What do you mean by the lucky alive person in the circle?
We have to find that person who is alive till the end after following all the processes of killing.
- What can be the other approach to solve this problem?
There are other variations to solve this problem. That could be that you are given in the question the number of steps you have to take to reach out to another person.
- Why is even value not the answer?
According to our problem statement, we have to kill the consecutive person. So the sword initially will always be on '1', which results in the killing of even values in the first round only.
In this blog, we have covered this problem correctly along with code in Java. If you want to learn more variations of this problem, you can practice on Practice Josephus Problem, Josephus, or take more references from other variations of Josephus Problem.