algoadvance

Leetcode 390. Elimination Game

Problem Statement

You are given an integer n. An elimination game is played with this sequence: start with the list [1, 2, 3, …, n]. At every step, eliminate every second number until only one number remains. You must find this last remaining number.

Here’s how the game is played:

Example:

Input: n = 9
Output: 6
Explanation:
Start with [1, 2, 3, 4, 5, 6, 7, 8, 9]
After removing every second element (left-to-right): [2, 4, 6, 8]
After removing every second element (right-to-left): [2, 6]
After removing every second element (left-to-right): [6]

Clarifying Questions

  1. Is the input always a positive integer?
    • Yes, n is always a positive integer.
  2. What is the range of n?
    • Typically, n can be any positive integer up to (10^9).
  3. Do I need to consider large inputs and optimize accordingly?
    • Yes, optimizing for large inputs up to (10^9) is necessary, indicating a need for an efficient approach.

Strategy

To solve this problem efficiently, a direct simulation approach where we generate and eliminate elements is impractical for large values of n due to time and space constraints. Instead, we can use a mathematical approach:

  1. Initial Setup: Start by setting a head that represents the remaining number.
  2. Keep Track of Steps and Direction: Steps will double after each complete traversal and will alternate directions.
  3. Adjust Head: Depending on the direction, adjust the head position accordingly.

Tail Recursive Approach:

  1. Each elimination round can be simplified by recognizing patterns rather than removing elements. Observing how the sequence shrinks and the remaining head position after each complete iteration helps.
  2. Implement the logic to identify these sequences using iterative adjustments.

Time Complexity

The time complexity is O(log n) due to iterative halving of the sequence length with each pass.

Code

Here’s the Java code for this approach:

public class Solution {
    public int lastRemaining(int n) {
        boolean left = true; // Starting direction
        int head = 1; // The head of the sequence
        int step = 1; // The initial step size
        int remaining = n; // The remaining count of numbers
        
        while (remaining > 1) {
            // If we eliminate from the left, or we're at an odd count, the head moves
            if (left || remaining % 2 == 1) {
                head += step;
            }
            // Halve the number of remaining elements
            remaining /= 2;
            // Double the step size (as we shrink the sequence)
            step *= 2;
            // Alternate the direction
            left = !left;
        }
        
        return head;
    }

    public static void main(String[] args) {
        Solution sol = new Solution();
        System.out.println(sol.lastRemaining(9)); // Output should be 6
    }
}

Explanation:

  1. Head Initialization: head starts at 1, representing the first element of the sequence.
  2. Loop: While more than one element remains, the process continues:
    • Adjust the head depending on the direction and whether the count of remaining elements is odd.
    • Halve the remaining number of elements.
    • Double the step to reflect the distance between the first element of each subsequent sequence.
    • Toggle the left variable to alternate the elimination direction.

By following this optimized approach, the solution efficiently determines the last remaining number even for very large values of n.

Cut your prep time in half and DOMINATE your interview with AlgoAdvance AI