Problem Description

You start with a list containing all integers from 1 to n in strictly increasing order: [1, 2, 3, ..., n].

You need to repeatedly eliminate numbers from this list following a specific pattern until only one number remains:

1. First elimination (left to right): Start from the leftmost number, remove it, then skip the next number, remove the following one, skip the next, and so on until you reach the end of the list.

2. Second elimination (right to left): Now work from the rightmost number of the remaining list, remove it, skip the previous number, remove the one before that, skip the previous, and continue this pattern until you reach the beginning.

3. Continue alternating: Keep alternating between left-to-right and right-to-left eliminations, always removing every other number starting from the appropriate end.

4. Stop when one remains: Continue this process until only a single number is left in the list.

For example, if n = 9:

• Initial: [1, 2, 3, 4, 5, 6, 7, 8, 9]
• After 1st elimination (L→R): [2, 4, 6, 8] (removed 1, 3, 5, 7, 9)
• After 2nd elimination (R→L): [2, 6] (removed 8, 4)
• After 3rd elimination (L→R): [6] (removed 2)
• Result: 6

Given an integer n, return the last remaining number after applying this elimination process.

Intuition

Instead of actually removing elements from a list, we can track the first and last remaining elements after each elimination round. The key insight is that we don't need to maintain the entire list - we only need to know the boundaries and the pattern of elimination.

After each elimination round:

• The number of remaining elements is halved (since we remove every other element)
• The distance between consecutive remaining elements doubles
• The first and last elements change based on the elimination direction and whether we have an odd or even count

Let's think about what happens to the boundaries:

• Left-to-right elimination: The first element always gets removed, so the new first element moves forward by the current step size. The last element only changes if we have an odd count (since we'd remove it in that case).
• Right-to-left elimination: The last element always gets removed, so it moves backward by the step size. The first element only changes if we have an odd count.

We can track:

• a1: The first element in the current remaining sequence
• an: The last element in the current remaining sequence
• step: The distance between consecutive elements (doubles after each round)
• cnt: The count of remaining elements (halves after each round)
• i: Round counter to determine the direction (even = left-to-right, odd = right-to-left)

The algorithm updates these values after each elimination:

• When going left-to-right (i is even): Update a1 by adding step, and if count is odd, also update an
• When going right-to-left (i is odd): Update an by subtracting step, and if count is odd, also update a1

We continue until only one element remains (cnt == 1), at which point a1 and an converge to the same value - our answer.

Solution Approach

The solution implements the boundary tracking approach we discussed in the intuition. Here's how the algorithm works:

Initialize variables:

• a1 = 1: First element of the current sequence
• an = n: Last element of the current sequence
• i = 0: Round counter (even means left-to-right, odd means right-to-left)
• step = 1: Distance between consecutive elements in the current sequence
• cnt = n: Number of elements remaining

Main loop (while cnt > 1):

For each elimination round, we update the boundaries based on the direction:

1. Right-to-left elimination (i % 2 == 1):
   • The last element is always removed: an -= step
   • If the count is odd, the first element also changes: if cnt % 2: a1 += step
2. Left-to-right elimination (i % 2 == 0):
   • The first element is always removed: a1 += step
   • If the count is odd, the last element also changes: if cnt % 2: an -= step

After updating boundaries:

• Halve the count: cnt >>= 1 (equivalent to cnt = cnt // 2)
• Double the step size: step <<= 1 (equivalent to step = step * 2)
• Increment round counter: i += 1

Return the result: When the loop ends (cnt == 1), both a1 and an point to the same value - the last remaining number. The solution returns a1.

Example walkthrough with n = 9:

• Initial: a1=1, an=9, step=1, cnt=9
• Round 0 (L→R): a1=2, an=8, step=2, cnt=4
• Round 1 (R→L): a1=2, an=6, step=4, cnt=2
• Round 2 (L→R): a1=6, an=6, step=8, cnt=1
• Return: 6

The time complexity is O(log n) since we halve the count in each iteration, and space complexity is O(1) as we only use a constant amount of variables.

Example Walkthrough

Let's walk through the solution with n = 7 to see how the boundary tracking approach works:

Initial Setup:

• List: [1, 2, 3, 4, 5, 6, 7]
• Variables: a1=1, an=7, step=1, cnt=7, i=0

Round 0 (Left-to-Right, i=0):

• We're eliminating from the left, removing every other element starting with the first
• Elements removed: 1, 3, 5, 7
• Remaining: [2, 4, 6]
• Updates:
  • a1 = 1 + 1 = 2 (first element always moves forward by step)
  • Since cnt=7 is odd: an = 7 - 1 = 6 (last element also changes)
  • cnt = 7 >> 1 = 3 (halve the count)
  • step = 1 << 1 = 2 (double the step)
  • i = 1

Round 1 (Right-to-Left, i=1):

• We're eliminating from the right, removing every other element starting with the last
• Elements removed: 6, 2
• Remaining: [4]
• Updates:
  • an = 6 - 2 = 4 (last element always moves backward by step)
  • Since cnt=3 is odd: a1 = 2 + 2 = 4 (first element also changes)
  • cnt = 3 >> 1 = 1 (halve the count)
  • step = 2 << 1 = 4 (double the step)
  • i = 2

Result:

• cnt = 1, so we exit the loop
• Both a1 and an equal 4
• Return 4

The key insight is that we never actually maintain the list - we just track where the boundaries are after each elimination. The step variable tells us the spacing between remaining elements, and we update boundaries based on the elimination direction and whether we have an odd count of elements.

Solution Implementation

Time and Space Complexity

Time Complexity: O(log n)

The algorithm uses a while loop that continues as long as cnt > 1. In each iteration:

• cnt is halved (cnt >>= 1), which means cnt is divided by 2
• Starting from n, the value is repeatedly halved until it reaches 1
• This results in approximately log₂(n) iterations

Each iteration performs only constant time operations (arithmetic operations, comparisons, and bit shifts), so the overall time complexity is O(log n).

Space Complexity: O(1)

The algorithm uses only a fixed number of variables:

• a1 and an to track the first and last elements
• i as a counter for iterations
• step to track the step size
• cnt to track the remaining count

No additional data structures are used, and the space usage doesn't depend on the input size n. Therefore, the space complexity is constant, O(1).

Common Pitfalls

1. Incorrect Boundary Update Logic

The most common mistake is incorrectly determining when to update the first or last element based on the direction and count parity.

Pitfall Example:

# INCORRECT: Updating wrong boundary or wrong condition
if iteration % 2 == 0:  # Left to right
    first_element += step_size
    last_element -= step_size  # Wrong! Should only update if odd count

Why it's wrong: When eliminating from left to right with an even count, the last element doesn't change. For example, [1,2,3,4] → [2,4]. The last element remains at position 4.

Correct Approach:

if iteration % 2 == 0:  # Left to right
    first_element += step_size
    if remaining_count % 2 == 1:  # Only update last if odd count
        last_element -= step_size

2. Off-by-One Error in Step Size Update

Another pitfall is updating the step size at the wrong time or by the wrong amount.

Pitfall Example:

# INCORRECT: Updating step before boundary updates
while remaining_count > 1:
    step_size *= 2  # Wrong timing!
    if iteration % 2 == 1:
        last_element -= step_size  # Now using wrong step size
        # ...

Correct Approach: Always update boundaries first using the current step size, then update the step size for the next iteration:

while remaining_count > 1:
    # First: Update boundaries with current step
    if iteration % 2 == 1:
        last_element -= step_size
        # ...
  
    # Then: Update step for next iteration
    step_size *= 2
    remaining_count //= 2
    iteration += 1

3. Confusion Between Direction and Iteration Number

It's easy to mix up which iteration number corresponds to which direction.

Pitfall Example:

# INCORRECT: Confusing iteration 0 as right-to-left
if iteration % 2 == 0:  # Thinking this is right-to-left
    last_element -= step_size  # Wrong direction logic

Remember:

• Iteration 0 (even) = Left to Right (removes first element always)
• Iteration 1 (odd) = Right to Left (removes last element always)

Debugging Tip: Add comments or use descriptive variable names:

is_left_to_right = (iteration % 2 == 0)
if is_left_to_right:
    first_element += step_size
    # ...

4. Not Handling Edge Cases

Failing to consider when n = 1 or very small values.

Solution: The algorithm naturally handles n = 1 since the while loop condition remaining_count > 1 prevents any iterations, correctly returning 1. However, always verify edge cases during implementation.