Explanation
Logical and Intuitive Approach
We can see that if the number of persons in a circle is a power of two, the person who starts the game will live. This is because after each round of murder, the number of individuals left will be reduced by two, and there will be no survivors; therefore, the next round will begin with the same person who began the game. This will continue.
Here the number of individuals in the circle is not a power of two. The person holding the gun will win in the first round when the number of people alive becomes a power of two because he is practically starting a game with people left in the power of two. So, for a total of 100, 36 people must die while 64 remain, which is a number less than the provided amount and a power of two. When the number of persons still alive reaches 64, the 36th person to be shot will be the 72nd person, and the 73rd person will have the gun.
Code Implementation Approach
Here, we can define a 100element array with values ranging from 1 to 100.
No. 1 is armed with a gun. He kills the next guy (number 2) and hands the gun to the third (i.e., no. 3).
Assume that each array element is a person. The first person shoots the second. So, starting with 1, we'll eliminate the following element, which is 2.
The first person then passes the gun to the next person, i.e., 3. That individual will then kill the next person, and so on. Such that, in an array, we must begin with 1 and eliminate every other (alternative) entry until we reach 100. (All even numbers will be eliminated from the array, leaving only odd numbers).
 1st Round  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
 2nd Round  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
 3rd Round  1, 9, 17, 25, 33, 41, 49, 57, 65, 73, 81, 89, 97
 4th Round  9, 25, 41, 57, 73, 89
 5th Round  9, 41, 73
 6th Round  9, 73

7th Round  73
Algorithm
To avoid the abovementioned manual computation below is the generic formula:
Step 1: To find the "Power of 2" that is greater than N for a given value of N. Let us refer it as P in short.
Step 2: To subtract N from the (P1). Let's label it as M, i.e., M = (P  1)  N.
Step 3: To multiply M by two, for example, M*2
Step 4: To subtract M*2 from the P1. Let's label it as 'result', i.e., result = (P1)  (M*2)
As a result, the individual with the number "result" will be the last who will live.
Code in C++
#include <bits/stdc++.h>
using namespace std;
int main(){
int person = 100;
// The placeholder array for the person
vector<int> arr(person);
// To assign placeholders from 1 to N (total person)
for (int i = 0; i < person; i++) {
arr[i] = i + 1;
}
// To start the game from the 1st person (Which is at placeholder 0)
int pos = 0;
// The game will be continued till we end up with only 1 person left
while (arr.size() > 1) {
// The current person will shoot the person next to
// him/her. So this will increment the position.
pos++;
// Since the person is standing in a circular manner, the person at last place
//has the right neighbor at placeholder 0. Therefore we are taking modulo to make it circular.
pos %= arr.size();
// Killing the person at placeholder 'pos'
// For that we simply remove that element
arr.erase(arr.begin() + pos);
// Therefore there is no need to increment the pos again to
// pass the gun as by erasing the element at
// 'pos', the next person will be at 'pos'.
}
// To print the person that survives the game in the end
cout << "The person that survives the game in the end: " << arr[0];
return 0;
}
You can also try this code with Online C++ Compiler
Run Code
Output
Code in Python
person = 100
# Placeholder array for person
arr = [0] * person
# To assign placeholders from 1 to N (total person)
for i in range(person):
arr[i] = i + 1
# It will start the game from 1st person (which will be at placeholder 0)
pos = 0
# The game will be continued till we end up with
# only one person left
while (len(arr) > 1):
# The current person will shoot the person next to him/her. So incrementing the position.
pos += 1
# Since person are standing in a circular manner
# for person at last place has the right neighbour
# at placeholder 0. Therefore we are taking modulo
# to make it circular.
pos %= len(arr)
# For killing the person at the placeholder 'pos'
# For that we remove that element
del arr[pos]
# Here is no need to increment the pos again to
# pass the gun as by erasing the element at
# 'pos', the next person will be at 'pos'.
# The person that survives the game in the end
print('The person that survives the game in the end:', arr[0])
You can also try this code with Online Python Compiler
Run Code
Output
Code in Java
import java.io.*;
import java.util.Arrays;
class Main {
public static void main (String[] args) {
int person = 100;
// The placeholder array for the person
int[] arr = new int[person];
// To assign placeholders from 1 to N (total person)
for (int i = 0; i < person; i++) {
arr[i] = i + 1;
}
// It will start the game from 1st person (Which is at
// placeholder 0)
int pos = 0;
// The game will be continued till we end up with only one
// person left
while (arr.length > 1)
{
// The current person will shoot the person next to
// him/her. So incrementing the position.
pos++;
// Since person are standing in circular manner, for
// person at last place has the right neighbour at
// placeholder 0. Therefore we are taking modulo to make it
// circular
pos %= arr.length;
// For killing the person at placeholder 'pos'
// For that we remove that element
int[] anotherArray = new int[arr.length  1];
System.arraycopy(arr, 0, anotherArray, 0, pos);
System.arraycopy(arr, pos + 1, anotherArray, pos,arr.length  pos  1);
arr = anotherArray;
// Here is no need to increment the pos again to
// pass the gun as by erasing the element at
// 'pos', hence the next person will be at 'pos'.
}
// To print Person that survives the game
System.out.println("The person that survives the game in the end: "+ arr[0]);
}
}
You can also try this code with Online Java Compiler
Run Code
Output
Frequently Asked Questions
What are â€˜100 people in a circle with a gunâ€™ problem?
100 persons are arranged in a circle in numerical sequence from 1 to 100. Number one has a gun. He then shoots the next person (No. 2) and hands over the gun to the next (i.e., No. 3). Everyone does the same thing until just one person lives. We have to find out which number is the last to survive.
What are the different forms of reasoning puzzles?
Box puzzle
Blood relation puzzle
Floor puzzle
Direction sense puzzle
Scheduling puzzle
Seating arrangement (square, triangular, circular, parallel, and linear), etc.
In how many rounds do the 100 people in a circle with a gun problem finishes?
The problem finishes in 7 rounds, and the 73rd person is the person to be alive at last.
How do problemsolving skills help us?
Problemsolving allows us to recognize and act on opportunities in the environment and exert (some) control over the future. Individuals and organizations equally require problemsolving abilities and the problemsolving process regularly.
What do we learn from problemsolving?
In summary, the definition of problemsolving abilities is this: the ability to recognize the nature of an issue, deconstruct it (break it down), and devise an effective set of activities to handle the obstacles it poses.
Conclusion
In this blog, we learned about the puzzle problem of 100 people in a circle with a gun with a solution approach.
This problem is quite similar to the Josephus problem and we have utilized the most elementary concept that we can use to solve this question by just simulating what happens through the process, we are able to reach a conclusive answer.
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 Interview Puzzles, 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!