Dare2Solve
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.
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.
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.head
by step
.remaining
by 2 as half of the numbers are eliminated.step
size.left
).head
.O(log n)
since we halve the number of elements in each step.
O(1)
as we use constant extra space.
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;
}
};
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
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;
}
}
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;
};