Giả sử chúng ta có một danh sách các số nguyên được sắp xếp từ 1 đến n. Đó là bắt đầu từ bên trái và kết thúc ở bên phải, chúng ta phải xóa số đầu tiên và mọi số khác sau đó cho đến khi chúng ta đến cuối danh sách. Chúng tôi sẽ lặp lại bước trước đó một lần nữa, nhưng lần này từ phải sang trái, loại bỏ số gần nhất bên phải và mọi số khác khỏi các số còn lại. Chúng tôi sẽ lặp lại các bước một lần nữa, xen kẽ từ trái sang phải và từ phải sang trái, cho đến khi còn lại một số duy nhất. Chúng ta phải tìm số cuối cùng vẫn bắt đầu bằng danh sách có độ dài n.
Vì vậy, nếu đầu vào là n =9, thì các bước sẽ như sau -
-
1 , 2, 3 , 4, 5 , 6, 7 , 8, 9
-
2, 4 , 6, 8
-
2 , 6
-
6
Vì vậy, câu trả lời sẽ là 6.
Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -
-
left:=1, head:=1, step:=1, rem:=n
-
trong khi rem> 1
-
nếu left khác 0 hoặc rem là số lẻ, thì head:=head + step
-
step:=step * 2
-
left:=inverse of left
-
rem:=rem / 2
-
-
quay trở lại đầu
Ví dụ (C ++)
Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn -
#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
int lastRemaining(int n) {
int head = 1;
int step = 1;
int rem = n;
int left = 1;
while(rem > 1){
if(left || rem % 2 == 1){
head += step;
}
step *= 2;
left = !left;
rem /= 2;
}
return head;
}
};
main(){
Solution ob;
cout << (ob.lastRemaining(9));
} Đầu vào
9
Đầu ra
6