algoadvance

Leetcode 390. Elimination Game

Problem Statement

You are given an integer n. An elimination game involves an array of integers from 1 to n. The game will be played based on the following rules:

  1. Start with the first element and remove every second element until the end of the array.
  2. Repeat the above step from left to right, then switch to right to left, and so on, until only one element remains.
  3. Return the last remaining element in the array.

For example, given n = 9, the elimination steps are as follows:

  1. [1, 2, 3, 4, 5, 6, 7, 8, 9], remove every second element -> [2, 4, 6, 8]
  2. [2, 4, 6, 8], remove every second element from right to left -> [2, 6]
  3. [2, 6], remove every second element from left to right -> [6]

The last remaining element is 6.

Clarifying Questions

  1. Can n be zero or negative?
    • No, n is guaranteed to be a positive integer.
  2. Should I consider the performance of the solution?
    • Yes, the solution should be efficient even for large values of n.

Strategy

To solve this problem, we need to recognize a pattern or adopt a mathematical approach rather than simulating the entire process, which would be inefficient for large values of n.

Let’s break down the approach:

  1. Start with the initial elimination step, which removes every second element.
  2. Keep track of the start position, remain number of elements, and the step interval.
  3. Adjust these variables based on the direction (left-to-right or right-to-left) and continue until only one element remains.

The approach maintains the invariant that after each full sequence of eliminations, the problem reduces in size but stays consistent in structure.

Code

Here is the C++ code to solve the problem:

class Solution {
public:
    int lastRemaining(int n) {
        int left = 1;
        int step = 1;
        bool fromLeft = true;
        
        while (n > 1) {
            // If we are eliminating from the left or the number of elements remaining is odd
            if (fromLeft || n % 2 == 1) {
                left += step;
            }
            // Double the step size and halve the number of elements remaining
            step *= 2;
            n /= 2;
            // Switch direction
            fromLeft = !fromLeft;
        }
        
        return left;
    }
};

Time Complexity

The time complexity of this solution is O(log n) because in each step, the size of the problem is halved. This logarithmic complexity ensures that the solution is efficient even for very large values of n.

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