Elimination Game - Practice Coding Problems

Elimination Game - Problem

Math Recursion Medium

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 again, alternating left to right and right to left, until a single number remains.

Given the integer n, return the last number that remains in arr.

Input & Output

Example 1 — Small Case

$ Input: n = 9

› Output: 6

💡 Note: arr = [1,2,3,4,5,6,7,8,9]. Round 1 (L→R): remove 1,3,5,7,9 → [2,4,6,8]. Round 2 (R→L): remove 8,4 → [2,6]. Round 3 (L→R): remove 2 → [6].

Example 2 — Even Number

$ Input: n = 10

› Output: 8

💡 Note: arr = [1,2,3,4,5,6,7,8,9,10]. Round 1 (L→R): remove 1,3,5,7,9 → [2,4,6,8,10]. Round 2 (R→L): remove 10,6,2 → [4,8]. Round 3 (L→R): remove 4 → [8].

Example 3 — Minimum Case

$ Input: n = 1

› Output: 1

💡 Note: Only one element [1], no elimination needed, return 1.

Constraints

1 ≤ n ≤ 10⁹

Visualization

Tap to expand

Understanding the Visualization

Input Array

Start with [1,2,3,4,5,6,7,8,9,10]

Elimination Process

Alternately remove every other element from left and right

Mathematical Tracking

Track first element and step size: O(log n) solution

Key Takeaway

🎯 Key Insight: Track the position mathematically instead of simulating the entire elimination process

Asked in

G Google 35 M Microsoft 28 A Amazon 22

The key insight is to track only the first remaining element and step size instead of simulating the entire array. The mathematical pattern approach achieves O(log n) time and O(1) space by recognizing that we only need to update the first element when going left-to-right or when the remaining count is odd.

Common Approaches

Approach	Time	Space	Notes
✓ Mathematical Pattern	O(log n)	O(1)	Track only the first element and step size without storing the array
Simulation	O(n log n)	O(n)	Simulate the entire elimination process using an actual array

Mathematical Pattern — Algorithm Steps

Initialize first=1, step=1, remaining=n, leftToRight=true
While remaining > 1
If going left-to-right or odd remaining, update first
Double the step size
Halve remaining elements
Toggle direction

Visualization

Tap to expand

Step-by-Step Walkthrough

Initialize

first=1, step=1, remaining=10, leftToRight=true

Round 1

first=1+1=2, step=2, remaining=5, leftToRight=false

Round 2

first=2+2=4, step=4, remaining=2, leftToRight=true

Result

first=4+4=8, remaining=1, return 8

Code -

solution.c — C

#include <stdio.h>
#include <stdbool.h>

int solution(int n) {
    int first = 1;
    int step = 1;
    int remaining = n;
    bool leftToRight = true;
    
    while (remaining > 1) {
        if (leftToRight || remaining % 2 == 1) {
            first += step;
        }
        
        step *= 2;
        remaining /= 2;
        leftToRight = !leftToRight;
    }
    
    return first;
}

int main() {
    int n;
    scanf("%d", &n);
    int result = solution(n);
    printf("%d\n", result);
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(log n)

Each iteration eliminates half the remaining elements, so we need log n iterations

⚡ Linearithmic

Space Complexity

O(1)

Only stores a few integer variables regardless of input size

✓ Linear Space

28.5K Views

Medium Frequency

~25 min Avg. Time

842 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Mathematical Pattern — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler