🎨Now live: Try our Free AI Image Generation Feature

Description
The problem involves repeatedly eliminating numbers from a list of integers from 1
to n
by alternating directions (left to right, then right to left) and removing every second number until only one number remains. The task is to determine the last remaining number.
Intuition
The key observation is that the first number (head
) changes whenever we eliminate numbers from left to right or when the number of remaining elements is odd during right-to-left elimination. The step size also doubles after every elimination.
Approach
- Initialize variables:
-
left
to indicate the direction of elimination (starting from the left). -remaining
for the count of remaining numbers. -step
to track the current step size. -head
to track the first remaining number in the current sequence. - In each iteration of the while loop:
- If eliminating from the left or the number of remaining elements is odd, increment the
head
bystep
. - Divideremaining
by 2 as half of the numbers are eliminated. - Double thestep
size. - Toggle the direction (left
). - Repeat until only one number remains, which is stored in
head
.
Complexity
Time Complexity:
O(log n)
since we halve the number of elements in each step.
Space Complexity:
O(1)
as we use constant extra space.
Code
C++
class Solution {
public:
int lastRemaining(int n) {
bool left = true;
int remaining = n;
int step = 1;
int head = 1;
while (remaining > 1) {
if (left || remaining % 2 == 1) {
head += step;
}
remaining /= 2;
step *= 2;
left = !left;
}
return head;
}
};
Python
class Solution:
def lastRemaining(self, n: int) -> int:
left = True
remaining = n
step = 1
head = 1
while remaining > 1:
if left or remaining % 2 == 1:
head += step
remaining //= 2
step *= 2
left = not left
return head
Java
class Solution {
public int lastRemaining(int n) {
boolean left = true;
int remaining = n;
int step = 1;
int head = 1;
while (remaining > 1) {
if (left || remaining % 2 == 1) {
head += step;
}
remaining /= 2;
step *= 2;
left = !left;
}
return head;
}
}
JavaScript
var lastRemaining = function (n) {
let left = true;
let remaining = n;
let step = 1;
let head = 1;
while (remaining > 1) {
if (left || remaining % 2 === 1) {
head = head + step;
}
remaining = Math.floor(remaining / 2);
step *= 2;
left = !left;
}
return head;
};