The elimination process can be modeled recursively. At each round, the problem size halves, and the direction alternates. The key is to realize that after each pass, the remaining numbers form an arithmetic progression, and the problem can be reduced to a smaller instance.
Instead of recursion, we can simulate the process iteratively by tracking the head, step, and direction. This avoids recursion and is more space-efficient.
classSolution {
publicintlastRemaining(int n) {
int head = 1, step = 1, remaining = n;
boolean left =true;
while (remaining > 1) {
if (left || remaining % 2 == 1) head += step;
remaining /= 2;
step *= 2;
left =!left;
}
return head;
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
classSolution {
funlastRemaining(n: Int): Int {
var head = 1var step = 1var left = truevar remaining = n
while (remaining > 1) {
if (left || remaining % 2==1) head += step
remaining /=2 step *=2 left = !left
}
return head
}
}
1
2
3
4
5
6
7
8
9
10
classSolution:
deflastRemaining(self, n: int) -> int:
head, step, left, remaining =1, 1, True, n
while remaining >1:
if left or remaining %2==1:
head += step
remaining //=2 step *=2 left =not left
return head
1
2
3
4
5
6
7
8
9
10
11
12
13
14
impl Solution {
pubfnlast_remaining(n: i32) -> i32 {
let (mut head, mut step, mut left, mut remaining) = (1, 1, true, n);
while remaining >1 {
if left || remaining %2==1 {
head += step;
}
remaining /=2;
step *=2;
left =!left;
}
head
}
}