Lucky Alive Person in a Circle

Introduction

This problem is based on the very famous Josephus Problem. Josephus, well he had his reasons as to why he would want to know this unlike us he might not have had a lot of time to think about it. There is a back story with this problem interested people could find it out on their own. So well like any other problem this one also has multiple ways how we can solve it. Let's get right to it.

Problem Statement

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

Output: 1

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.

Problem illustration to find the luckiest person

Solution Approach

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)	Luckiest Person(w)
1	1
2	1
3	3
4	1
5	3
6	5
7	7
8	1

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^xwhere the luckiest number will again be 1.

Recommended: Try the Problem yourself before moving on to the solution

Implementation

Every number can be represented in the form of 2.

For example:

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 finding the answer.

We can verify this also with the help of an image:

So yaa '5' is the right answer.

C++

#include<bits/stdc++.h>
using namespace std;
int luckiest(int N){
  // static variables 
   int ans = 1, s = 0;

   while (N > 1) {
      ++s;
      ans += (N & 1) << s;
      N >>= 1;
   }
   return ans;
}
// Main Method

int main() {
    int n = 19;
    cout << luckiest(n);
}

Java

public class Main {
    public static void main(String[] args) {
        int n = 19;
        System.out.println(luckiest(n));
    }
    public static int luckiest(int N){
       int ans = 1, s = 0;

       while (N > 1) {
          ++s;
          ans += (N & 1) << s;
          N >>= 1;
       }
       return ans;
    }
}

Python

def luckiest(n: int):
    ans = 1
    s = 0
 
    while (n > 1):
        s += 1
        ans += (n & 1) << s
        n >>= 1
 
    return ans
n = 19
print(luckiest(n))

Output

Complexity Analysis

Time Complexity

This is the most efficient approach to solve this problem. The time complexity to solve this problem is O(1).

Space Complexity

Space complexity is O(1) as no extra space is required by the bits.

Let's wrap up this blog and move toward the FAQs section.

Also see, Euclid GCD Algorithm

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 killing processes.

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.

Conclusion

In this blog, we discussed the dilemma of Josephus and its solution i.e. Lucky Alive Person in a Circle in different languages.