สมมติว่าเรามีอาร์เรย์ที่เรียกว่า nums โดยที่ nums[i] ถูกเขียนบนกระดานดำ Ram และ Sam ผลัดกันลบหนึ่งองค์ประกอบออกจากกระดาน โดยที่ Ram เริ่มก่อน หากการลบตัวเลขทำให้ XOR ระดับบิตขององค์ประกอบทั้งหมดของกระดานดำกลายเป็น 0 ผู้เล่นคนนั้นจะแพ้ Bitwise XOR ขององค์ประกอบหนึ่งคือองค์ประกอบนั้น และ XOR ระดับบิตที่ไม่มีองค์ประกอบใดๆ จะเป็น 0 หากผู้เล่นคนใดเริ่มเทิร์นด้วย XOR ระดับบิตขององค์ประกอบทั้งหมดของกระดานดำเท่ากับ 0 ผู้เล่นนั้นจะเป็นผู้ชนะ สมมติว่าอาร์เรย์ถือ [1, 2, 1] ดังนั้น Ram สามารถลบ 1 หรือ 2 หาก Ram ลบ 1 อาร์เรย์จะเป็น [2,1] เนื่องจาก XOR ขององค์ประกอบ 1 XOR 2 =3 ตอนนี้ Sam สามารถทำได้ ลบองค์ประกอบใด ๆ เพราะ Ram จะเป็นคนลบองค์ประกอบสุดท้ายและเขาจะสูญเสีย ถ้าเขาเลือก 2 เพื่อลบก่อน อาร์เรย์จะกลายเป็น [1,1] XOR เป็น 0 ดังนั้น Ram จะสูญเสีย
เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้ -
- n :=ขนาดของ nums
- x :=0
- สำหรับองค์ประกอบทั้งหมด i เป็น nums −
- x :=x XOR ฉัน
- ผลตอบแทน 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
