Solution
If person 1 has a sword, then he will kill the person next to it and then pass the sword.
We can solve it by brute force( we will understand a better solution later in this article). Surviving persons after each round of killing are written in the table below. We can simply do it this way, but what will be the efficient solution?
In Round 1: 1, 3, 5, 7, 9, 11, 13, 15, 17, 19, 21, 23, 25, 27, 29, 31, 33, 35, 37, 39, 41, 43, 45, 47, 49, 51, 53, 55, 57, 59, 61, 63, 65, 67, 69, 71, 73, 75, 77, 79, 81, 83, 85, 87, 89, 91, 93, 95, 97, 99
In Round 2: 1, 5, 9, 13, 17, 21, 25, 29, 33, 37, 41, 45, 49, 53, 57, 61, 65, 69, 73, 77, 81, 85, 89, 93, 97
In Round 3: 1, 9, 17, 25, 33, 41, 49, 57, 65, 73, 81, 89, 97
In Round 4: 9, 25, 41, 57, 73, 89
In Round 5: 9, 41, 73
Here 9 kills 41 and passes the sword to 73.
In Round 6: 9, 73
73 kills 9, therefore being the only surviving person.
In Round 7: 73
So the answer will be 73.
Now let’s discuss a more intuitive and efficient solution.
(This will also generalize the solution, and you can do it for numbers greater than 100). The question is a variation of ‘The Josephus Problem’ in which one person has to choose a seat/position in a circle to protect himself from being killed.
Try solving the problem for the powers of 2, n=2,4,16,32,64,128,...
Every time we can observe that person 1 will survive(if he starts the game) since the number of people gets halved in every round, and the last person will again pass the sword to 1. It’s quite a simple observation: the survivor will be the person who starts the game. It can be 1 if he starts or some other number starting the game, provided the number of people is in the power of 2.
Now consider this: if we have a game with more than a power of two players, as we are killing people, the number of players will inevitably be reduced to a power of two at some point. The person wielding the sword will be the sole survivor at that point. In a game with 2n players, this is effectively the first player.
Starting with 100 players, we'll need to eliminate 36 of them to get down to a power of two (64). Since we start at player 2, the last person we need to kill is player 72, who will be killed by player 71, and the first person to win in the effective power of two games will be player 73.
(It's worth noting that, regardless of the number of persons, the process of reducing to a power of two is always completed in the first round, but why?)
Consider X persons, and Y is the highest power of 2 less than or equal to Y.
2 * (X - Y) + 1 is the surviving person.
Check out this problem - 8 Queens Problem
Frequently Asked Questions
Who will win if person 5 starts the game and there are 32 people?
It's quite simple, since 32 is a power of two, person 5 will win the game. After every round, people will be halved, and 5 will be starting the game.
Who will survive the game if there are 41 people and 1 starts the game?
It will be number 19. We can also do it by the above-discussed formula, 2(x-y)+1, which will be equal to 2*(41-32)+1=19, x is the total number of people, and y is the highest power of 2 less than y.
Why should I practice puzzles?
Puzzles help you to improve your logical and problem-solving skills. Moreover, they are also asked in company interviews.
Do MNCs ask puzzles in the interview of IT companies?
Many tech giants like Google, Microsoft, etc., ask the puzzles in the interview process as they want to check your logical thinking.
From where can I practice more such puzzles?
You can refer to the key takeaways section for links to puzzle sections.
Conclusion
In this article, we discussed a famous puzzle, 100 people in a circle with a sword. We talked about its brute force solution and a more efficient and intuitive approach and also derived a formula for it, therefore generalizing the problem. We hope that you enjoyed the puzzle, and this blog helped you to understand the puzzle well.
Recommended Readings:
Do check out The Interview guide for Product Based Companies as well as some of the Popular Interview Problems from Top companies like Amazon, Adobe, Google, etc. on Coding Ninjas Studio.
Also check out some of the Guided Paths on topics such as Data Structure and Algorithms, Competitive Programming, Operating Systems, Computer Networks, DBMS, System Design, etc. as well as some Contests, Test Series, Interview Bundles, and some Interview Experiences curated by top Industry Experts only on Coding Ninjas Studio.
Do upvote our blog to help other ninjas grow.
Happy Learning!
8+ registered 