ধরুন আমাদের nums নামে একটি অ্যারে আছে, যেখানে একটি চকবোর্ডে nums[i] লেখা আছে। রাম এবং স্যাম পালা করে চকবোর্ড থেকে ঠিক একটি উপাদান মুছে ফেলে, রাম প্রথমে শুরু করে। যদি একটি সংখ্যা মুছে ফেলার ফলে চকবোর্ডের সমস্ত উপাদানের বিটওয়াইজ XOR 0 হয়ে যায়, তাহলে সেই প্লেয়ারটি হেরে যায়। একটি উপাদানের বিটওয়াইজ XOR হল সেই উপাদানটি নিজেই, এবং কোনও উপাদানের বিটওয়াইজ XOR 0 নয়৷ যদি কোনও খেলোয়াড় 0 এর সমান চকবোর্ডের সমস্ত উপাদানগুলির বিটওয়াইজ XOR দিয়ে তাদের পালা শুরু করে, তবে সেই খেলোয়াড়টি জিতবে৷ ধরুন অ্যারেটি [1, 2, 1] ধরে রেখেছে, তাই রাম 1 বা 2 সরিয়ে ফেলতে পারে, যদি Ram 1 সরিয়ে দেয়, তাহলে অ্যারেটি হবে [2,1], কারণ 1 XOR 2 =3 উপাদানগুলির XOR, এখন স্যাম করতে পারে যেকোনো উপাদান মুছে ফেলুন, কারণ রাম শেষ উপাদানটি মুছে ফেলবেন এবং তিনি হারাবেন।, যদি তিনি প্রথমে সরানোর জন্য 2 বেছে নেন, তাহলে অ্যারেটি হয়ে যায় [1,1], XOR হল 0, তাই রাম হারাবে।
এটি সমাধান করতে, আমরা এই পদক্ষেপগুলি অনুসরণ করব -
- n :=সংখ্যার আকার
- x :=0
- সমস্ত উপাদানের জন্য i সংখ্যায় −
- x :=x XOR i
- রিটার্ন 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;
}
};
main(){
Solution ob;
vector<int> v = {1,2,1};
cout << (ob.xorGame(v));
} ইনপুট
{1,2,1} আউটপুট
0
