Question

Problem Statement

Josephus attended a party where they had a rather strange raffle. Everyone was to stand in a circle, and every M^th person was to be eliminated until only one person was remaining, who won the lawnmower.

Write the function Josephus, which takes as parameters a vector<string> representing the N guests at the party in the order they line up for the raffle, and the integer M, giving which person will be eliminated at each turn. Your function should return a string giving the name of the winner of the raffle (the last person standing).

Hint: While there is a mathematical solution, a queue will be much more straightforward.

Constraints

• N, the length of the vector<string> guests, will be greater than 0 and less than 2,000.
• M will be greater than zero and less than 2,000.

Examples

1. guests = {"Josephus", "Titus", "Simon", "Eleazar"}
   M = 3 
   Returns: "Josephus"

   Counting every third person from Josephus (remember, they are in a circle), Simon is eliminated first. Skipping Eleazar and Josephus, Titus goes next. Skipping Eleazar and Josephus, we come back to Eleazar. Josephus, who cleverly suggested M = 3, comes out the winner!

2. guests = {"Bradford", "Rosette", "Ji", "Ashleigh", "Avery", "Lavonna", "Fredericka"} 
   M = 2 
   Returns: "Fredericka"

3. guests = {"Tiffany", "Randy", "Kit", "Sharlene", "Marquerite", "Debra", "Pok", "Tanisha", "Claudio"} 
   M = 17 
   Result: "Debra"

Given Function

string Josephus(vector<string> guests, int M) {
// your code here
}

Use the given function to solve the problem statement. Please follow the given notes and constraints. Please code this problem in C++.

Answer 1

#include <iostream>
#include <vector>
using namespace std;
string Josephus(vector<string> guests, int M) {
int startPosition = 0; /*to hold the value to know where to start counting initally it is 0*/
while(guests.size()>1){
int nextElemToDelete = startPosition;
nextElemToDelete +=(M);
nextElemToDelete%=guests.size(); //circular counting after last element start from zero
nextElemToDelete = (nextElemToDelete-1); //index of vector starts at 0 so we have to substract 1.
if(nextElemToDelete==-1){//if nextElemToDelete ==-1 we have to delete last element
nextElemToDelete = guests.size()-1; // setting nextElemToDelete last element
}
guests.erase(guests.begin()+nextElemToDelete);
startPosition = nextElemToDelete;
}
return guests[0];
}
int main()
{
vector<string> guests;
//guests = {"Josephus", "Titus", "Simon", "Eleazar"};
guests = {"Tiffany", "Randy", "Kit", "Sharlene", "Marquerite", "Debra", "Pok", "Tanisha", "Claudio"} ;
//guests = {"Bradford", "Rosette", "Ji", "Ashleigh", "Avery", "Lavonna", "Fredericka"};
string a = Josephus(guests,17);
cout<<a;

return 0;
}