get the index of an element from the original list and the value of the remaining element

Question

I'm trying to solve a Josephus problem where, in addition to the value of the remaining element, I need to return its index in the original list. I implemented the list myself and it works well, I get the value correctly, but I can’t figure out how to get the index from the original array!
Can anyone explain this to me please?

My code:

#include "circular_linked_list.h"

enum class direction { clockwise, counterclockwise };

template<typename T>
std::pair<int, T> Josephus_problem(CircularLinkedList<T> list, direction dir, unsigned step) {
    if (list.getLength() == 0) {
        throw std::invalid_argument("List is empty");
    }

    int currentIndex = 0;
    int size = list.getLength();
    int finalIndex = 0;
    while (list.getLength() > 1) {
        if (dir == direction::counterclockwise) {
            finalIndex -= step + 1;//???
            currentIndex = (currentIndex - step + 1) % list.getLength();
        } else {
            finalIndex += step - 1;//???
            currentIndex = (currentIndex + step - 1) % list.getLength();
        }

        list.removeAt(currentIndex);
    }

    finalIndex = ...;//Don't know what to do here!
    return {finalIndex, list[0]};
}

Answer 1

Pretty much this:

Initialize a std::list of unsigned integers (size_t) that represent the index of each element in the list from 0 to N-1.

std::list<size_t> listOfPositions;
size_t N = <how ever many elements are in your original list>
for (size_t i = 0; i < N; i++) {
    listOfPositions.push_back(i);
}

Then just iterate through the list one by one. Each time you hit the STEPth element, you erase it. You can take advantage of the fact that list.erase on a position element will return the next item after.

Here's the simple logic:

unsigned int index = 1;
auto pos = listOfPositions.begin();

while (listOfPositions.size() > 1) {
    if (index == step) {
        pos = listOfPositions.erase(pos); // returns the next item in the list
        index = 1;
    }
    else {
        pos++;
        index++;
    }

    if (pos == listOfPositions.begin()) {
        pos = listOfPositions.end();
    }
}

And you can take advantage of reverse iterators for the counterclockwise operations. Some small tweaks to the above logic to make it work for reverse iterations.

unsigned int index = 1;
auto pos = listOfPositions.rbegin() + N - 1; // point to the first item in the list
while (listOfPositions.size() > 1) {
    if (index == step) {
        pos = listOfPositions.erase(pos); // return the previous item in the list when using reverse iterators
        index = 1;
    }
    else {
        pos++;
        index++;
    }

    if (pos == listOfPositions.rend()) {
        pos = listOfPositions.rbegin();
    }
}

In both cases, the "last remaining index" is this:

size_t last_remaining = *pos;