Elimination Game

Problem

There is a list of sorted integers from 1 to n. Starting from left to right, remove the first number and every other number afterward until you reach the end of the list.

Repeat the previous step again, but this time from right to left, remove the right most number and every other number from the remaining numbers.

We keep repeating the steps again, alternating left to right and right to left, until a single number remains.

Find the last number that remains starting with a list of length n.

Example:

Input:
n = 9,
1 2 3 4 5 6 7 8 9
2 4 6 8
2 6
6

Output:
6

Solution

Recording Head Solution: O(log N) time

public class Solution {
    public int lastRemaining(int n) {
        int start = 1, step = 1, remain = n;
        boolean right = true;
        while (remain > 1) {
            if (right || remain % 2 == 1) start += step;
            remain /= 2;
            step *= 2;
            right = !right; 
        }
        return start;
    }
}

Analysis

Instead of imitation the process of eliminating num
We solve this problem by recording only the start number
We update the start in each eliminating process and return start when there is only one number left
We know we move the start to right when it's in right direction or in left direction with odd numbers
For example given 1 -> 2 -> 3 -> 4 -> 5 -> 6
When it's in right, we will have remain / 2 numbers left and start becomes 2
Like this: 2 -> 4 -> 6, then we go left and remove 6 and 4
start = 4 now, which exactly passes step = 2 steps