edaBit-coding-challenges/Josephus-Permutation/code.cpp

/*  A group of n prisoners stand in a circle awaiting execution.
 *  Starting from an arbitrary position(0), the executioner kills
 *  every kth person until one person remains standing, who is then granted
 *  freedom (see examples).
 *  Create a function that takes 2 arguments — the number of people to
 *  be executed n, and the step size k, and returns the original position
 *  (index) of the person who survives.
 */
#include <numeric>;
int whoGoesFree(int n, int k) {
    //  create an index of positions
    std::vector<int> indexP(n) ;
    std::iota (std::begin(indexP), std::end(indexP), 0);
    //  position of last person killed; c is count to k;
    int lastkill = 0, c = 0, target = 0;
    //  kill everybody
    while(n){
        //  if killing, kill and advance target
         if(++c == k){
             lastkill = indexP[target];
             //  this advances the target
             indexP.erase(indexP.begin() + target);
             c = 0;
             n--;
         }
         //  advance the target
         else{//  determine who might get killed next
             target = ++target % indexP.size();}
        }
    return lastkill;
}