1에서 n까지 정렬된 정수 목록이 있다고 가정합니다. 그것은 왼쪽에서 시작하여 오른쪽에서 끝나는 것이므로 목록의 끝에 도달할 때까지 첫 번째 숫자와 다른 모든 숫자를 나중에 제거해야 합니다. 이전 단계를 다시 반복하지만 이번에는 오른쪽에서 왼쪽으로 가장 오른쪽 숫자와 나머지 숫자에서 다른 모든 숫자를 제거합니다. 하나의 숫자가 남을 때까지 왼쪽에서 오른쪽으로, 오른쪽에서 왼쪽으로 교대로 단계를 다시 반복합니다. 길이가 n인 목록으로 시작하여 남아 있는 마지막 숫자를 찾아야 합니다.
따라서 입력이 n =9와 같으면 단계는 다음과 같습니다. -
-
1 ,2,3 ,4,5 ,6,7 ,8,9
-
2,4 ,6,8
-
2 ,6
-
6
따라서 답은 6이 됩니다.
이 문제를 해결하기 위해 다음 단계를 따릅니다. −
-
왼쪽:=1, 헤드:=1, 단계:=1, rem:=n
-
rem> 1
동안-
왼쪽이 0이 아니거나 rem이 홀수이면 head :=head + step
-
단계 :=단계 * 2
-
왼쪽 :=왼쪽의 반대
-
렘 :=렘 / 2
-
-
머리 반환
예시(C++)
더 나은 이해를 위해 다음 구현을 살펴보겠습니다. −
#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));
} 입력
9
출력
6