100 people in a circle with a gun

Q: What are the different forms of reasoning puzzles?

Box puzzleBlood relation puzzleFloor puzzleDirection sense puzzleScheduling puzzleSeating arrangement (square, triangular, circular, parallel and linear), etc.

Q: 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.

Introduction

Puzzles are good exercise for the brain. They help in enhancing the cognitive abilities of the brain helping with Problem Solving and related skills. There are numerous types of puzzles; each one having a logic inherent to itself which helps in cracking it. A good puzzle well is actually like a good mystery that we may have read about or watched on TV. It has the finest of hints which help in reaching its solution.

The following article discusses one such puzzle so let's get right to it.

Problem Statement

Let us look at the problem statement of 100 people in a circle with a gun.

100 persons are arranged in a circle in numerical sequence from 1 to 100. The 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. Which number is the last to survive?

There are a total of 100 people, numbered from 1 to 100.

Answer

The 73rd individual will live at the end(in the 7th round).

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 100-element 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 above-mentioned 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 (P-1). 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 P-1. Let's label it as 'result', i.e., result = (P-1) - (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 problem-solving skills help us?

Problem-solving allows us to recognize and act on opportunities in the environment and exert (some) control over the future. Individuals and organizations equally require problem-solving abilities and the problem-solving process regularly.

What do we learn from problem-solving?

In summary, the definition of problem-solving 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: