algoadvance

You have a list arr of all integers in the range [1, n] sorted in a strictly increasing order. Apply the following algorithm on arr:

• 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 rightmost number and every other number from the remaining numbers.
• Keep repeating the steps, alternating left to right and right to left, until a single number remains.

Find the last number that remains after performing the described operations.

Example:

Input: n = 9
Output: 6

Explanation:
n = 9, [1, 2, 3, 4, 5, 6, 7, 8, 9]
1st pass: [2, 4, 6, 8]
2nd pass: [2, 6]
3rd pass: [6]

Clarifying Questions

1. What is the range of n?
   • Usually, this can go up to (10^7) or more in LeetCode problems.
2. Can n be less than 1?
   • As per usual problem constraints, ( n \geq 1 ).

Strategy

To achieve an efficient solution:

1. Use mathematical insight instead of simulating the entire process.
2. Note that each round of elimination halves the problem size.
3. We can determine which end will provide the elimination perspective and count the elimination step.

Code

Below is the code implementation:

def lastRemaining(n: int) -> int:
    left = True
    remaining = n
    head = 1
    step = 1
    
    while remaining > 1:
        if left or remaining % 2 == 1:
            head += step
        remaining //= 2
        step *= 2
        left = not left
    
    return head

#Example usage:
print(lastRemaining(9)) # Output: 6

Time Complexity

The time complexity of this solution is ( O(\log n) ) because we are reducing the problem size by half each step until only one element remains. This is highly efficient compared to a direct simulation, which would have a much larger time complexity.

Try our interview co-pilot at AlgoAdvance.com

• Got blindsided by a question you didn’t expect?

• Spend too much time studying?

• Or simply don’t have the time to go over all 3000 questions?