Scale Engineer

Elimination Game

Med
#0377Time: 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: 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.1 company
Patterns
MathRecursion
Companies
Autodesk

Prompt

[Fetch error]

Approaches

3 approaches with complexity analysis and trade-offs.

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.

Walkthrough

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

Time

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

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.

Trade-offs

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.

Solutions

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 walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next →

Next problem