We have to find the last element not marked in a list after certain operations. Operations are performed until only one element is left.
Suppose I have a list which has certain elements 'marked' alternatively after a particular index $x$. For example, I begin with list: $[a, b, c, d, e, f', g, h', i]$ and $x=5$. The compliment symbol(or dash, whatever you call it) represents that this element is marked. Currently the last element not marked is $i$. Now every not marked element can mark the next not marked element. We always begin from the first index in the list. So, we begin from index $1$ and find that $a$ itself is not marked. Hence $a$ marks the next not marked element which is $b$. The next not marked element is $c$ which marks $d$ and so on. When we reach $e$, the next not marked element is $g$ so it is marked too. The last element, as we see, will not be marked by anyone. Also, since it's the last element it cannot mark anyone. After one iteration our list now becomes: $[a, b', c, d', e, f', g', h', i]$. The last element not marked after our first iteration is $i$.
For our second iteration we again begin with index $1$ and see that $a$ is not marked. $a$ hence marks next not marked element, which is $c$. $e$ marks $i$. Our list becomes: $[a, b', c', d', e, f', g', h', i']$. This time our last not marked element is $e$.
Finally $a$ will mark $e$ and $a$ will be our last remaining element. So for every iteration we have to find the last not marked element in the list till only one element is left and no more iterations can be performed.
Some things I concluded: The first element, here $a$, will always be the last element remaining. Also, the same element will be the last element not marked as in our previous iteration if the not marked elements is odd in our current iteration(Here it happened for our first iteration, $i$ was the last not marked element). I also found some similarities with Josephus problem but couldn't really connect it. I think there will be some recurrence relation connecting the indices and the number of not marked elements for a particular iteration.
I am hoping for some closed formula that can directly give me the index of the last not marked element or maybe some efficient technique rather than just brute force.
First eliminate all elements marked before the first step.
Then, from the remaining elements, notice that after iteration k, the remaining numbers are on the positions $m\cdot2^k+1$, $m=0,1,\ldots$
So if you have $n$ unmarked elements in the beginning, the index of the last one in the reduced array will be for $m=\left\lfloor\frac{n-1}{2^k}\right\rfloor$
Of course, you have to map this index back into the original array in which you ignored the already marked elements.