Lucky Alive Person in a Circle

Introduction

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.

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.

 

 

 

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

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 find 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

7

 

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.

Frequently Asked Questions

  1. 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. 
  2. 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.
  3. 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.

Key Takeaways

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 ProblemJosephus, or take more references from other variations of Josephus Problem.

Keep coding!

Was this article helpful ?
0 upvotes

Comments

No comments yet

Be the first to share what you think