Last remaining number

Problem: There is a list of sorted integers from 1 to n. Starting from left to right, remove the first number and every alternate number afterward till the end of the list.

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

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 = 11
1 2 3 4 5 6 7 8 9 10 11
2 4 6 8 10
2 8
8

Output:
8

Approach: To understand the approach, let's run through the example given above which is when n is 11. Let's see the numbers in the list:

[1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11]

Here the leftmost number say left is 1 and rightmost number say right is 11. Right. After the first pass what will happen? Obviously left will become 2 which is the next available number from left and right will become 10 the next available number from the right. 

What would have happened if n was 10, rightmost element was 10 initially and even after the 1st pass it would be 10 only. If you run through more examples you will find that only in case the number of elements are odd, rightmost element will change to the next available number. Obviously left will always change as the pass begins from leftmost number.

Fine so now the remaining numbers are [2, 4, 6, 8, 10]. After the second pass, left will become 4 and end will become 8. Actually it follows the same logic as above, this time just from right to left. That means right will always be changed but left will only be changed if number of elements are odd.

So after the second pass the remaining numbers are [4, 8]. Now we need to run the same logic from left to right. After this pass left will become 8 (next available number) but right will not be changed as the number of elements are even so right will remain 8 only.

Now you can see only one element is remaining which is 8. It is our answer. 

Good so till now we understood that in case of left to right pass, left will be changed to next available number and right will only be changed to next available number in case of number of elements are odd and similarly in case of right to left pass, right will be changed to next available number and left will be changed only in case of number of elements are odd.

Now another thing to notice is that after every pass we are eliminating half of the number of elements. That means if before a pass the number of elements were n, after the pass number of elements will become n/2.

We are almost ready with our solution, except one thing how to efficiently get the next available number from left and right. Let's go back to our example and try to observe the pattern.

[1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11] left = 1, right = 11

[2, 4, 6, 8, 10] left = 2 (1 + 1), right = 10 (11 - 1) 

[4, 8] left = 4 (2 + 2), right = 8 (10 - 2)

[8] left = 8 (4 + 4) right = 8

Did you find that pattern? After every pass, if we are modifying left or right, they are getting modified with 2 ^ (n  -1) where the n is the number of passes happened till now. That means After nth pass if left and right need to be modified then they will be modified as:

• left = left + 2 ^ (n - 1)
• right = right - 2 ^ (n - 1)

Why? If you see after every pass we are eliminating half of the number of elements and also we are removing every alternate number.

With this knowledge, here is our algorithm:

• Left = 1
• Right = n
• Jump = 1
• WHILE n > 1 
• IF left to right
• Left = Left + Jump
• IF n is odd
• Right = Right - Jump
• ELSE IF right to left
• Right = Right - Jump
• IF n is odd
• Left = Left + Jump
• n = n / 2
• Jump = Jump * 2
• Return Left

That's it!

Implementation in C#:

        public static int LastRemaining(int n)

        {

            int left = 1;

            int right = 1;

            int jump = 1;

            int elementsRemaining = n;

            bool fromLeft = true;

            while(elementsRemaining > 1)

            {

                if (fromLeft)

                {

                    left += jump;

                    right = elementsRemaining % 2 == 0 ? right : right - jump; 

                }

                else

                {

                    right -= jump;

                    left = elementsRemaining % 2 == 0 ? left : left + jump;

                }

                elementsRemaining /= 2;

                fromLeft = !fromLeft;

                jump *= 2;

            }

            return left;

        }

Complexity: log(n)