390. Elimination Game
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:
- Begin with the first element in the list and then remove every other element. This is considered a left-to-right pass.
- On the next iteration, start from the end of the remaining list and remove every other element, moving right to left.
- 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.
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, thestep
doubles since every second element is removed.cnt
: The count of remaining numbers in the list. Initially the same asn
, and it is halved after each pass (cnt >>= 1
is equivalent tocnt = 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 increasea1
bystep
. For odd passes (i
is 1, 3, 5, ...), we reducean
bystep
only. - If the count of remaining numbers is odd (
cnt % 2
), then on every passan
is decremented for eveni
anda1
is incremented for oddi
. - After processing the current pass, we double the step (
step <<= 1
is equivalent tostep = 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).
Ready to land your dream job?
Unlock your dream job with a 2-minute evaluator for a personalized learning plan!
Start EvaluatorExample 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, andcnt
to 10. - First Pass (i = 0, left-to-right): We increment
a1
bystep
since it's an even pass, soa1
becomes 2. Thestep
doubles to 2, andcnt
is halved to 5.- Updated list would look like
[2, 4, 6, 8, 10]
if we were removing elements, but we're not.
- Updated list would look like
- Second Pass (i = 1, right-to-left): Now, it's an odd pass and
cnt
is odd, soan
(last number) is decremented bystep
, becoming 10 - 2 = 8. We double thestep
to 4, and halvecnt
to 2.- The conceptual list would now be
[2, 6]
.
- The conceptual list would now be
- Third Pass (i = 2, left-to-right): For this even pass, we increase
a1
again bystep
, resulting ina1
= 2 + 4 = 6. The step is doubled to become 8, andcnt
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
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.
Which data structure is used to implement priority queue?
Recommended Readings
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 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 Your Personal Dijkstra's Algorithm to Landing Your Dream Job The goal of AlgoMonster is to help you get a job in the shortest amount of time possible in a data driven way We compiled datasets of tech interview problems and broke them down by patterns This way we
Got a question? Ask the Monster Assistant anything you don't understand.
Still not clear?  Submit the part you don't understand to our editors. Or join our Discord and ask the community.