LeetCode 390: Elimination Game Solution in Python – A Step-by-Step Guide

What Is LeetCode 390: Elimination Game?

LeetCode 390: Elimination Game gives you an integer n, representing numbers from 1 to n arranged in a list. You eliminate every other number, starting left-to-right, then right-to-left, repeating until one number remains. Your task is to return that last number. It’s a problem that tests your ability to identify patterns or simulate eliminations efficiently!

Problem Statement

• Input:
• n: Integer representing the number of elements (1 to n).
• Output: Integer - The last remaining number.
• Rules:
• Start with list [1, 2, ..., n].
• Eliminate every other number (e.g., 1st pass: remove even indices).
• Alternate direction: left-to-right, then right-to-left, repeat.
• Continue until one number remains.

Constraints

• 1 <= n <= 10⁹

Examples

• Input: n = 9
• Output: 6
• [1,2,3,4,5,6,7,8,9] → [2,4,6,8] (left-to-right).
• [2,4,6,8] → [2,6] (right-to-left).
• [2,6] → [6] (left-to-right).
• Input: n = 6
• Output: 4
• [1,2,3,4,5,6] → [2,4,6] → [2,4] → [4].
• Input: n = 1
• Output: 1
• [1] → [1].

These show the elimination dance—let’s solve it!

Understanding the Problem: Finding the Last Number

To tackle LeetCode 390 in Python, we need to: 1. Simulate or deduce the elimination process from 1 to n. 2. Alternate directions (left-to-right, right-to-left). 3. Find the last remaining number efficiently.

A naive approach might simulate with a list, but that’s O(n²) and slow for n up to 10⁹. We’ll use:

• Best Solution: Mathematical pattern (Josephus variant)—O(log n) time, O(1) space—fast and optimal.
• Alternative Solution: Simulation with list—O(n²) time, O(n) space—intuitive but impractical.

Let’s deduce with the best solution!

Best Solution: Mathematical Pattern (Josephus Variant)

Why This Is the Best Solution

The mathematical pattern approach runs in O(log n) time with O(1) space by recognizing a recursive pattern in the elimination process, akin to the Josephus problem but with alternating directions. It’s the most efficient—avoiding simulation entirely and computing the result directly, making it ideal for large n!

How It Works

Think of it like a shrinking circle:

• Pattern:
• Left-to-right: Eliminate every 2nd number, survivor shifts based on remaining count.
• Right-to-left: Adjust based on parity and remaining numbers.
• Key Insight:
• For each step, halve the count (n //= 2).
• Track first number (head), update with step size (2^k).
• Direction alternates, affecting head adjustment.
• Formula:
• If n is odd and left-to-right, head stays or shifts.
• Recursively compute until n = 1.
• Result: Final head is the answer.

It’s like decoding the survivor’s position step-by-step!

Step-by-Step Example

For n = 9:

• Init: head = 1, n = 9, step = 1, left = True.
• Pass 1 (left-to-right):
• n = 9, odd, eliminate every 2nd: [2,4,6,8].
• head = 1 + step = 2, n = 9 // 2 = 4, step *= 2 = 2, left = False.
• Pass 2 (right-to-left):
• n = 4, even, [2,4,6,8] → [2,6].
• head = 2 (no shift for even right-to-left), n = 4 // 2 = 2, step *= 2 = 4, left = True.
• Pass 3 (left-to-right):
• n = 2, even, [2,6] → [2].
• head = 2 + step = 6, n = 2 // 2 = 1, step *= 2 = 8, left = False.
• n = 1: Return head = 6.
• Result: 6.

For n = 6:

• Init: head = 1, n = 6, step = 1.
• Pass 1: head = 2, n = 3, step = 2, left = False.
• Pass 2: head = 2 + 2 = 4, n = 1, step = 4, left = True.
• Result: 4.

Code with Explanation

Here’s the Python code using the mathematical pattern:

Copy codeclass Solution:
    def lastRemaining(self, n: int) -> int:
        # Initialize head, step, and direction
        head = 1
        step = 1
        left = True

        # Eliminate until one remains
        while n > 1:
            # Left-to-right or odd count from right
            if left or n % 2 == 1:
                head += step
            # Halve the count, double the step
            n //= 2
            step *= 2
            left = not left

        return head

Explanation

• Lines 4-6: head: First number, step: Elimination step, left: Direction.
• Lines 8-15: Loop until n = 1:
• If left-to-right or n odd (right-to-left), increment head by step—O(1).
• Halve n, double step, flip direction—O(1).
• Line 17: Return final head—O(1).
• Time: O(log n)—halves n each iteration.
• Space: O(1)—few variables.

This is like a pattern decoder—swift and sleek!

Alternative Solution: Simulation with List

Why an Alternative Approach?

The simulation solution runs in O(n²) time with O(n) space by explicitly eliminating numbers in a list, alternating directions. It’s intuitive—great for small n or understanding the process, but impractical for large n due to time complexity!

How It Works

• List: Initialize with 1 to n.
• Simulate:
• Left-to-right: Remove every 2nd element.
• Right-to-left: Reverse and repeat.
• Repeat: Until one remains.
• Result: Last number.

Step-by-Step Example

For n = 6:

• Init: List = [1, 2, 3, 4, 5, 6].
• Left-to-right: [2, 4, 6].
• Right-to-left: [2, 4] (remove 6).
• Left-to-right: [4].
• Result: 4.

Code with Explanation

Copy codeclass Solution:
    def lastRemaining(self, n: int) -> int:
        # Initialize list
        arr = list(range(1, n + 1))
        left = True

        # Eliminate until one remains
        while len(arr) > 1:
            if left:
                arr = arr[1::2]  # Every other from left
            else:
                arr = arr[-2::-2] if len(arr) % 2 == 0 else arr[-1::-2]  # From right
            left = not left

        return arr[0]

Explanation

• Line 4: arr: List of 1 to n—O(n).
• Line 5: left: Direction flag.
• Lines 7-12: Eliminate:
• Left: Take every 2nd element—O(n).
• Right: Reverse slice based on parity—O(n).
• Line 14: Return last element—O(1).
• Time: O(n²)—n eliminations, O(n) per step.
• Space: O(n)—list.

It’s a brute-force eliminator—clear but slow!

Comparing the Two Solutions

• Mathematical Pattern (Best):
• Time: O(log n)—logarithmic.
• Space: O(1)—minimal.
• Pros: Fast, space-efficient, scalable.
• Cons: Pattern-based, less intuitive.
• Simulation (Alternative):
• Time: O(n²)—quadratic.
• Space: O(n)—list.
• Pros: Easy to follow.
• Cons: Slow, memory-heavy.

Math pattern wins for efficiency!

Additional Examples and Edge Cases

• n=1: Both return 1.
• n=2: Both return 2.
• Large n: Math scales, simulation lags.

Math is optimal, simulation works for small n.

Complexity Breakdown

• Math Pattern:
• Time: O(log n).
• Space: O(1).
• Simulation:
• Time: O(n²).
• Space: O(n).

Math excels for performance.

Key Takeaways

• Math Pattern: Decode the survivor—fast and lean!
• Simulation: Play it out—clear but slow!
• Elimination: Patterns beat brute force.
• Python Tip: Logic rocks—see [Python Basics](/python/basics).

Final Thoughts: Find That Survivor

LeetCode 390: Elimination Game in Python is a pattern challenge. The mathematical approach is the efficiency champ, while simulation offers a tangible alternative for small cases. Want more? Try LeetCode 62: Unique Paths or LeetCode 384: Shuffle an Array. Ready to eliminate? Visit Solve LeetCode 390 on LeetCode and find that last number today!