390. Elimination Game

MediumRecursionMath
Leetcode Link

Problem Description

In this problem, you have a sorted list of integers from 1 to n. You apply a specific elimination algorithm to this list that consists of repeatedly removing numbers in a particular order until only one number remains. The rules for the removal process are as follows:

  1. Begin with the first element in the list and then remove every other element. This is considered a left-to-right pass.
  2. On the next iteration, start from the end of the remaining list and remove every other element, moving right to left.
  3. Continue this process, alternating between left-to-right and right-to-left, until there is only one number left in the list.

The task is to determine what that last remaining number will be given the integer n.

Intuition

To find the solution without simulating the entire elimination process (which would be inefficient for large n), we can observe patterns in the list as we remove numbers. We notice that on each pass, the number of elements in the list is halved. Therefore, we can track the following variables throughout the process:

  • a1: The first number left in the list after each pass.
  • an: The last number left in the list after each pass.
  • i: The index of the current pass, starting from 0.
  • step: The distance between remaining numbers after each pass.
  • cnt: The count of remaining numbers after each pass.

The critical insight is that we can mathematically determine the new values of a1 and an without explicitly simulating each pass. Specifically, a1 increments by step on every pass, and an decrements by step when the pass starts from the right and the count of remaining numbers is odd. We continue this process until cnt (the count of remaining numbers) is reduced to 1, which indicates only one number is left. At that point, a1 will be the last remaining number, and we can return it.

By tracking these variables and updating them after each pass in an alternating fashion, we arrive at the last number without having to actually remove elements from the list, which significantly reduces the time complexity and allows us to solve the problem with a high efficiency.

Learn more about Recursion and Math patterns.

Not Sure What to Study? Take the 2-min Quiz to Find Your Missing Piece：

Which two pointer techniques do you use to check if a string is a palindrome?

Solution Approach

The solution implemented in Python uses a straightforward loop to simulate the process of elimination described above, without actually removing elements from a list. Instead, we use variables to keep track of the state of the list. Below is the detailed explanation of how the implementation corresponds to the solution approach:

We initially set a1 to 1, an to n, i to 0, step to 1, and cnt to n. These variables represent the start and end of the list, the index of the pass (which determines the direction of elimination), the gap between numbers after each iteration, and the count of numbers remaining, respectively.

  • a1: This variable represents the value of the first element in the remaining list.
  • an: Represents the value of the last element in the remaining list.
  • i: Used to track the number of completed passes, and it helps to determine the direction of the current pass.
  • step: The distance between consecutive remaining numbers. On each pass, the step doubles since every second element is removed.
  • cnt: The count of remaining numbers in the list. Initially the same as n, and it is halved after each pass (cnt >>= 1 is equivalent to cnt = cnt // 2).

The loop continues until cnt becomes 1, which means there's only one number left. Inside the loop:

  • On each iteration, we check if the pass is odd (i % 2) or even. For even passes (i is 0, 2, 4, ...), we always increase a1 by step. For odd passes (i is 1, 3, 5, ...), we reduce an by step only.
  • If the count of remaining numbers is odd (cnt % 2), then on every pass an is decremented for even i and a1 is incremented for odd i.
  • After processing the current pass, we double the step (step <<= 1 is equivalent to step = step * 2) because every other number was removed during the pass.
  • The count of remaining elements is halved (cnt >>= 1) as we effectively remove every second element in the list on each pass.
  • We increment i after each pass to alternate the direction for the next pass.

At the end of the loop, a1 is the last number remaining, which is what we return. The solution makes use of bitwise operations for efficiency, such as >>= for division by 2 and <<= for multiplication by 2. The algorithm efficiently tracks and updates the bounds of the remaining list without the need to maintain the list itself, resulting in a time complexity of O(log n).

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

Which of the following uses divide and conquer strategy?

Example Walkthrough

Let's walk through an example using the solution approach with n = 10. The sorted list from 1 to n will initially be [1, 2, 3, 4, 5, 6, 7, 8, 9, 10].

  • Initialization: We set a1 to 1, an to 10, i to 0, step to 1, and cnt to 10.
  • First Pass (i = 0, left-to-right): We increment a1 by step since it's an even pass, so a1 becomes 2. The step doubles to 2, and cnt is halved to 5.
    • Updated list would look like [2, 4, 6, 8, 10] if we were removing elements, but we're not.
  • Second Pass (i = 1, right-to-left): Now, it's an odd pass and cnt is odd, so an (last number) is decremented by step, becoming 10 - 2 = 8. We double the step to 4, and halve cnt to 2.
    • The conceptual list would now be [2, 6].
  • Third Pass (i = 2, left-to-right): For this even pass, we increase a1 again by step, resulting in a1 = 2 + 4 = 6. The step is doubled to become 8, and cnt is halved to 1.

Since cnt is now 1, there's only one number left, and a1 is that last remaining number which is 6. Hence, the last remaining number when using this elimination algorithm on a sorted list from 1 to 10 is 6.

1
2Let's illustrate the solution approach with a real example using `n = 10`. Initially, `a1` is set to 1, representing the first element in our sorted list `[1, 2, 3, 4, 5, 6, 7, 8, 9, 10]`.
3
4- In the first pass (left-to-right), we eliminate every other number, starting with the second one. We update `a1` to 2, double the `step` to 2, and halve the `cnt` to 5. We've conceptually eliminated numbers and now have `[2, 4, 6, 8, 10]`.
5- The second pass (right-to-left) starts with an odd count, so we decrease `an` by the current `step` value, which is 2, resulting in `an` = 8. Again, we double the step to 4 and halve the `cnt` to 2, leaving us with `[2, 6]`.
6- On the third pass (left-to-right), since it's even, we increase `a1` by the step (now 4) to get `a1` = 6. Doubling the step to 8 and halving the `cnt` to 1 means we're left with a single number: `6`.
7
8Therefore, the last standing number is `6` which we find by intelligently keeping track of the eliminated numbers' range and count without running through each elimination.

Solution Implementation

1class Solution:
2    def lastRemaining(self, n: int) -> int:
3        # Initialize the first and last elements
4        first_element, last_element = 1, n
5      
6        # Initialize iteration count, step increment, and count of remaining elements
7        iteration, step, remaining_count = 0, 1, n
8      
9        # Loop until only one element remains
10        while remaining_count > 1:
11            # If the iteration is odd, operate from the right (last to first)
12            if iteration % 2:
13                # If count is odd, decrement the last element
14                last_element -= step
15                # Adjust first element if the count is odd
16                if remaining_count % 2:
17                    first_element += step
18            # If the iteration is even, operate from the left (first to last)
19            else:
20                # Increment the first element
21                first_element += step
22                # Adjust the last element if the count is odd
23                if remaining_count % 2:
24                    last_element -= step
25          
26            # Halve the remaining count as we remove half of the elements each iteration
27            remaining_count >>= 1
28            # Double the step size since every round we skip one more element
29            step <<= 1
30            # Move to the next iteration
31            iteration += 1
32      
33        # The first element is the last remaining number
34        return first_element
35
1class Solution {
2    public int lastRemaining(int n) {
3        int firstElement = 1;      // Initialize the first element of the sequence to 1
4        int lastElement = n;       // Initialize the last element of the sequence to n
5        int step = 1;              // Step size, which doubles each iteration
6
7        // Loop until only one element remains. cnt keeps track of the remaining elements.
8        for (int round = 0, remainingElements = n; remainingElements > 1;
9             remainingElements >>= 1, step <<= 1, ++round) {
10          
11            // In odd rounds, move from right to left
12            if (round % 2 == 1) {
13                lastElement -= step;  // Subtract step from the last element
14
15                // If the count is odd, increment the first element
16                if (remainingElements % 2 == 1) {
17                    firstElement += step;
18                }
19            } 
20            // In even rounds, move from left to right
21            else {
22                firstElement += step;  // Increment first element
23              
24                // If the count is odd, decrement the last element
25                if (remainingElements % 2 == 1) {
26                    lastElement -= step;
27                }
28            }
29        }
30
31        // Once the loop is finished, there's only one element left, which is the first element.
32        return firstElement;
33    }
34}
35
1class Solution {
2public:
3    int lastRemaining(int n) {
4        int first = 1, last = n; // Initialize the first and last elements
5        int step = 1; // This will represent the step size after each round
6
7        // Loop until there's only one number remaining
8        for (int round = 0, remaining = n; remaining > 1; remaining >>= 1, step <<= 1, ++round) {
9            // In every odd round, update the last element
10            if (round % 2) {
11                last -= step; // Move the last element backwards by the step size
12                if (remaining % 2) {
13                    first += step; // If there's an odd number of elements, move the first element forwards
14                }
15            } else {
16                // In every even round, update the first element
17                first += step; // Move the first element forwards by the step size
18                if (remaining % 2) {
19                    last -= step; // If there's an odd number of elements, move the last element backwards
20                }
21            }
22        }
23        return first; // Return the remaining number
24    }
25};
26
1// Function to determine the last remaining number after eliminating every second element in rounds
2function lastRemaining(n: number): number {
3    let first: number = 1; // Initialize the first element
4    let last: number = n;  // Initialize the last element
5    let step: number = 1;  // This will represent the step size after each round
6
7    // Loop until there's only one number remaining
8    for (let round: number = 0, remaining: number = n; remaining > 1; remaining >>= 1, step <<= 1, round++) {
9        // In every odd round, update the last element
10        if (round % 2 === 1) {
11            last -= step; // Move the last element backwards by the step size
12            if (remaining % 2 === 1) {
13                first += step; // If there's an odd number of remaining elements, move the first element forwards
14            }
15        } else {
16            // In every even round, update the first element
17            first += step; // Move the first element forwards by the step size
18            if (remaining % 2 === 1) {
19                last -= step; // If there's an odd number of remaining elements, move the last element backwards
20            }
21        }
22    }
23    return first; // Return the remaining number
24}
25
26// Example usage 
27// let result = lastRemaining(10);
28// console.log(result);  // This would compute the result for n=10 and print it to the console
29
Not Sure What to Study? Take the 2-min Quiz：

Which two pointer techniques do you use to check if a string is a palindrome?

Time and Space Complexity

The given Python code defines a method lastRemaining that calculates the last number remaining after repeatedly removing numbers from a list that has been recreated at each step of the problem. In the problem, numbers are removed alternately from the start and end, and every second number from the list is removed at each step.

Time Complexity

The time complexity of the function is determined by the while loop which runs until cnt > 1. The number cnt represents the remaining numbers in the sequence and is halved (cnt >>= 1) at each iteration of the while loop due to removing every second number. As a result, the time complexity of the loop, and hence the function, is O(log n), as it reduces the sequence size by a factor of two at each step until only one number is left.

Space Complexity

The space complexity of the provided code is O(1). This is because the algorithm uses a fixed number of variables (a1, an, i, step, cnt) and doesn't require any additional space that would grow with the input size n. It does not utilize any complex data structures that would require space proportional to the input size.

Learn more about how to find time and space complexity quickly using problem constraints.

Fast Track Your Learning with Our Quick Skills Quiz:

Which of the following shows the order of node visit in a Breadth-first Search?

Recommended Readings

Recursion Review

Recursion Recursion is one of the most important concepts in computer science Simply speaking recursion is the process of a function calling itself Using a real life analogy imagine a scenario where you invite your friends to lunch https algomonster s3 us east 2 amazonaws com recursion jpg You first

Math Basics

Math for Technical Interviews How much math do I need to know for technical interviews The short answer is about high school level math Computer science is often associated with math and some universities even place their computer science department under the math faculty However the reality is that you

LeetCode Patterns - Top Patterns for Coding Interviews

Top Patterns to Conquer the Technical Coding Interview Should the written word bore you fear not A delightful video alternative awaits iframe width 560 height 315 src https www youtube com embed LW8Io6IPYHw title YouTube video player frameborder 0 allow accelerometer autoplay clipboard write encrypted media gyroscope picture in picture

Got a question? Ask the Teaching Assistant anything you don't understand.

Still not clear? Ask in the Forum,  Discord or Submit the part you don't understand to our editors.

←
↑TA 👨‍🏫