C++ code solution for puzzle : "100 people standing in a circle in an order 1 to 100. No. 1 has a sword. He kills the next person (i.e. No. 2) and gives the sword to the next (i.e. No. 3). All people do the same until only 1 survives. Which number survives at the last?"

Puzzle : 100 people standing in a circle in an order 1 to 100. No. 1 has a sword. He kills the next person (i.e. No. 2) and gives the sword to the next (i.e. No. 3). All people do the same until only 1 survives. Which number survives at the last?

Solution : There are many ways and better ways to solve the same problem with variable number of people suppose N. But I use brute force to create the solution in C++ program.


Here is the code :

#include <iostream>
#include <conio.h>

using namespace std;

/*
 Check for live pesons in array
*/
int GetIndex(int *arr, int SIZE, int startingAddress)
{
 while (true)
 {
  if (startingAddress >= SIZE) {
   startingAddress = 0;
  }

  if (arr[startingAddress] == -1) {
   ++startingAddress;
   continue;
  }
  else break;
 }

 return startingAddress;
}

/*
 Print only live peoples
*/
void printLivePeople(int *persons, int SIZE)
{
 for (int index = 0; index < SIZE; ++index)
 {
  if (persons[index] != -1)
   cout << persons[index] <<" ";
 }
}

void main()
{
 const int COUNT = 101;
 int persons[COUNT];

 for (int index = 0; index < COUNT; ++index) {
  persons[index] = index + 1;
 }

 int personsToDie = COUNT -1;
 int nextLivePerson = 0;

 while (personsToDie > 0) {
  int livePerson = GetIndex(persons, COUNT, nextLivePerson);
  nextLivePerson = GetIndex(persons, COUNT, ++livePerson);

  // Set -1 as dead people
  persons[nextLivePerson++] = -1;
  --personsToDie;
 }

 printLivePeople(persons, COUNT);

 cout << "\nDone";
  _getch();
}

Output (for 100 people)

73
Done

Thanks.

PS. Another solution to worth looking at link.