ภาพรวมปัญหา
สมมติว่ามีอาร์เรย์ nums ที่ตัวเลขถูกเขียนบนกระดานดินสอ ราม (Ram) และ แซม (Sam) สลับกันลบตัวเลขทีละ 1 ตัวจากกระดาน โดยรามเริ่มก่อน หากการลบตัวเลขทำให้ XOR แบบบิตของทุกตัวเลขบนกระดานกลายเป็น 0 ผู้เล่นคนนั้นจะแพ้ XOR ของ 1 ตัวคือตัวมันเอง XOR ของไม่มีตัวเลขคือ 0 หากผู้เล่นเริ่มเทิร์นด้วย XOR ของทุกตัวเลข = 0 ผู้เล่นคนนั้นจะชนะ
ตัวอย่าง
nums = [1, 2, 1] รามสามารถลบ 1 หรือ 2 ได้
- ถ้ารามลบ 1 → เหลือ [2,1] XOR = 3 แซมลบตัวไหนก็ได้ เพราะรามจะต้องลบตัวสุดท้ายและแพ้
- ถ้ารามลบ 2 → เหลือ [1,1] XOR = 0 รามแพ้ทันที
แนวทางแก้ปัญหา
สังเกตว่า: รามชนะได้ก็ต่อเมื่อ XOR ของทั้งอาร์เรย์ = 0 หรือ จำนวนตัวเลขเป็นจำนวนคู่
- n := ขนาดของ nums
- x := XOR ของทุกตัวใน nums
- คืนค่า true ถ้า x == 0 หรือ n % 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;
}
};
int main() {
Solution ob;
vector<int> v = {1, 2, 1};
cout << (ob.xorGame(v)); // 0 (false)
}
Input
{1,2,1}
Output
0
