Giả sử chúng ta có một mảng gọi là nums, trong đó nums [i] được viết trên bảng đen. Ram và Sam thay phiên nhau xóa chính xác một phần tử khỏi bảng đen, Ram bắt đầu trước. Nếu việc xóa một số làm cho XOR theo từng bit của tất cả các phần tử của bảng đen trở thành 0, thì người chơi đó sẽ thua. XOR theo chiều bit của một phần tử là chính phần tử đó và XOR theo chiều bit của không phần tử nào bằng 0. Nếu bất kỳ người chơi nào bắt đầu lượt của mình với XOR theo chiều bit của tất cả các phần tử của bảng đen bằng 0, thì người chơi đó sẽ thắng. Giả sử mảng đang giữ [1, 2, 1] nên Ram có thể loại bỏ 1 hoặc 2, nếu Ram loại bỏ 1 thì mảng sẽ là [2,1], vì XOR của các phần tử 1 XOR 2 =3, lúc này Sam có thể loại bỏ bất kỳ phần tử nào, vì Ram sẽ là người xóa phần tử cuối cùng và anh ta sẽ thua. Nếu anh ta chọn 2 để loại bỏ trước, thì mảng trở thành [1,1], XOR là 0, do đó Ram sẽ mất.
Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -
- n:=kích thước của nums
- x:=0
- cho tất cả các phần tử tôi trong nums -
- x:=x XOR tôi
- return x giống 0 hoặc n mod 2 là 0
Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn -
Ví dụ
#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));
} Đầu vào
{1,2,1} Đầu ra
0