Josephus Problem

/**
 * People are standing in a circle waiting to be executed. Counting begins at
 * a specified point in the circle and proceeds around the circle in a
 * specified direction. After a specified number of people are skipped, the
 * next person is executed. The procedure is repeated with the remaining
 * people, starting with the next person, going in the same direction and
 * skipping the same number of people, until only one person remains, and
 * is freed.
 *
 * The problem — given the number of people, starting point, direction, and
 * number to be skipped — is to choose the position in the initial circle to
 * avoid execution.
 *
 * https://en.wikipedia.org/wiki/Josephus_problem
*/

#include <iostream>

unsigned josephus1(const unsigned cnt, const unsigned start, const unsigned step)
{
    bool* dead = new bool[cnt] { false };

    unsigned exec_cnt = 0;
    unsigned step_cnt = 0;

    unsigned i;
    for (i = start % cnt; exec_cnt < cnt; i = (i + 1) % cnt) {
        if (!dead[i]) {
            step_cnt++;
            if (step_cnt == step) {
                dead[i] = true;

                std::cout << i << " ";

                exec_cnt++;
                step_cnt = 0;
            }
        }
    }

    std::cout << std::endl;

    delete[] dead;

    return (i - 1) % cnt;
}

unsigned josephus2(const unsigned cnt, const unsigned start, const unsigned step)
{
    unsigned* next = new unsigned[cnt];

    for (size_t i = 0; i < cnt; i++) {
        next[i] = (i + 1) % cnt;
    }

    unsigned counter = 0;
    unsigned last = 0;

    unsigned i;
    for (i = start % cnt; next[i] != i; i = next[i]) {
        counter++;

        if (counter == step) {
            std::cout << i << " ";
            next[last] = next[i];
            counter = 0;
        } else {
            last = i;
        }
    }

    std::cout << i << std::endl;

    delete[] next;

    return i;
}

int main(int argc, char const* argv[])
{
    unsigned ans = josephus1(10, 0, 3);
    std::cout << "The last one is " << ans << std::endl;

    ans = josephus2(10, 0, 3);
    std::cout << "The last one is " << ans << std::endl;

    return 0;
}