nums[i]가 칠판에 쓰여진 nums라는 배열이 있다고 가정합니다. 램과 샘은 교대로 칠판에서 정확히 하나의 요소를 지웁니다. 램이 먼저 시작됩니다. 숫자를 지우면 칠판의 모든 요소에 대한 비트 XOR이 0이 되면 해당 플레이어는 집니다. 한 요소의 비트 XOR은 해당 요소 자체이고 요소가 없는 비트 XOR은 0입니다. 어떤 플레이어가 칠판의 모든 요소에 대한 비트 XOR이 0인 상태에서 차례를 시작하면 그 플레이어가 승리합니다. 배열이 [1, 2, 1]을 보유하고 있어 Ram이 1 또는 2를 제거할 수 있다고 가정하고, Ram이 1을 제거하면 배열은 [2,1]이 됩니다. 왜냐하면 요소 1의 XOR 2 =3이기 때문에 이제 Sam은 다음을 수행할 수 있습니다. Ram은 마지막 요소를 지우고 그는 잃을 것이기 때문에 모든 요소를 제거하십시오. 그가 먼저 제거하기 위해 2를 선택하면 배열은 [1,1]이 되고 XOR은 0이 되므로 Ram은 잃게 됩니다.
이 문제를 해결하기 위해 다음 단계를 따릅니다. −
- n :=숫자 크기
- x :=0
- nums의 모든 요소 i에 대해 −
- x :=x XOR i
- 반환 x는 0과 같거나 n mod 2는 0입니다.
이해를 돕기 위해 다음 구현을 살펴보겠습니다. −
예
#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
bool xorGame(vector<int>& nums) {
int n = nums.size();
int x = 0;
for(int i : nums) x ^= i;
return x == 0 || n % 2 == 0;
}
};
main(){
Solution ob;
vector<int> v = {1,2,1};
cout << (ob.xorGame(v));
} 입력
{1,2,1} 출력
0