Code360 powered by Coding Ninjas X Naukri.com. Code360 powered by Coding Ninjas X Naukri.com
Table of contents
1.
Introduction
2.
Problem Statement
3.
Solution
4.
Frequently Asked Questions
4.1.
Who will win if person 5 starts the game and there are 32 people?
4.2.
Who will survive the game if there are 41 people and 1 starts the game?
4.3.
Why should I practice puzzles?
4.4.
Do MNCs ask puzzles in the interview of IT companies?
4.5.
From where can I practice more such puzzles?
5.
Conclusion
Last Updated: Mar 27, 2024

100 People in a Circle

Author Apoorv Dixit
0 upvote
Master Python: Predicting weather forecasts
Speaker
Ashwin Goyal
Product Manager @
Interview Puzzles

Introduction

Puzzles are critical thinking problems that test a person’s lateral thinking and problem-solving skills, similar to brain teasers. These types of puzzle questions are commonly used by interviewers to assess a potential employee's ability to solve complex problems using strategies and higher-order thinking in order to determine their fit for the company.

In this article, we will be discussing a famous puzzle- ‘100 people in a Circle with a sword.’ We will also generalize the solution for all such problems where the people may vary.

Problem Statement

Difficulty level: Easy

100 people are standing in a circle in order of 1 to 100.

No.1 has a sword. He kills the next person (i.e., no. 2) and passes the sword to the next (i.e., no. 3). 

All people do the same until only one survives.

Which number survives at last?

Get the tech career you deserve, faster!
Connect with our expert counsellors to understand how to hack your way to success
User rating 4.7/5
1:1 doubt support
95% placement record
Akash Pal
Senior Software Engineer
326% Hike After Job Bootcamp
Himanshu Gusain
Programmer Analyst
32 LPA After Job Bootcamp
After Job
Bootcamp

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!

Previous article
Marbles in the Jar
Next article
Gates of Heaven
Live masterclass