Elimination Game

MEDIUM

Description

[Fetch error]

Approaches

Checkout 3 different approaches to solve Elimination Game. Click on different approaches to view the approach and algorithm in detail.

Brute-Force Simulation

This approach directly simulates the elimination process as described in the problem. We use a dynamic list of numbers, and in each step, we iterate through the list to remove elements according to the rules, alternating the direction of removal until only one number is left.

Algorithm

Initialize a list (e.g., ArrayList in Java) with numbers from 1 to n.
Use a boolean flag, say leftToRight, initialized to true, to track the direction of elimination.
Start a loop that continues as long as the size of the list is greater than 1.
Inside the loop, if leftToRight is true, create a new list by taking every second element (at indices 1, 3, 5, ...) from the current list.
If leftToRight is false, create a new list by taking every second element starting from the end of the current list.
Replace the current list with the newly created list.
Flip the leftToRight flag.
Once the loop terminates, the list will contain a single element, which is the result.

The most straightforward way to solve the problem is to perform the simulation step-by-step. We can maintain a list of the numbers that are currently in the game. In each round, we create a new list containing only the numbers that survive the elimination. For a left-to-right pass, we keep the elements at odd-numbered positions (2nd, 4th, 6th, etc.). For a right-to-left pass, we do the same but starting from the end. We repeat this process, alternating directions, until our list contains only one number.

import java.util.ArrayList;
import java.util.List;

class Solution {
    public int lastRemaining(int n) {
        if (n == 1) {
            return 1;
        }
        List<Integer> numbers = new ArrayList<>();
        for (int i = 1; i <= n; i++) {
            numbers.add(i);
        }

        boolean leftToRight = true;
        while (numbers.size() > 1) {
            List<Integer> nextNumbers = new ArrayList<>();
            if (leftToRight) {
                for (int i = 1; i < numbers.size(); i += 2) {
                    nextNumbers.add(numbers.get(i));
                }
            } else { // rightToLeft
                for (int i = numbers.size() - 2; i >= 0; i -= 2) {
                    // Add to the front to maintain order
                    nextNumbers.add(0, numbers.get(i));
                }
            }
            numbers = nextNumbers;
            leftToRight = !leftToRight;
        }
        return numbers.get(0);
    }
}

Complexity Analysis

Time Complexity: O(N). The total number of operations across all passes is proportional to N + N/2 + N/4 + ... + 1, which is a geometric series that sums to O(N).Space Complexity: O(N). We need to store the list of numbers, which initially has `N` elements. In each step, we create a new list of about half the size.

Pros and Cons

Pros:

Simple to understand and implement.
Directly follows the problem description.

Cons:

Highly inefficient for large values of n.
Prone to Time Limit Exceeded (TLE) or Memory Limit Exceeded (MLE) errors on competitive programming platforms.

Code Solutions

Checking out 3 solutions in different languages for Elimination Game. Click on different languages to view the code.

class Solution {
public
  int lastRemaining(int n) {
    int a1 = 1, an = n, step = 1;
    for (int i = 0, cnt = n; cnt > 1; cnt >>= 1, step <<= 1, ++i) {
      if (i % 2 == 1) {
        an -= step;
        if (cnt % 2 == 1) {
          a1 += step;
        }
      } else {
        a1 += step;
        if (cnt % 2 == 1) {
          an -= step;
        }
      }
    }
    return a1;
  }
}

Video Solution

Watch the video walkthrough for Elimination Game

Patterns:

MathRecursion

Companies:

Autodesk |