12345678910111213141516171819202122232425262728293031 |
- /* 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;
- }
|