মনে করুন, nums নামক একটি অ্যারে আছে, যেখানে nums[i] চকবোর্ডে লেখা আছে। রাম এবং স্যাম পালা পালায় চকবোর্ড থেকে ঠিক একটি উপাদান মুছে ফেলে, রাম প্রথমে শুরু করে। যদি কোনো সংখ্যা মুছতে হলে সকল উপাদানের বিটওয়াইজ XOR ০ হয়ে যায়, তবে সেই খেলোয়াড় হয়ে পড়ে। একক উপাদানের বিটওয়াইজ XOR সেটি নিজে, এবং কোনো উপাদান নেই থাকলে XOR ০। যদি কোনো খেলোয়াড়র পালা শুরু হলে চকবোর্ডের সকল উপাদানের বিটওয়াইজ XOR ০ থাকে, তবে সে জিতবে।
মনে করুন অ্যারেটি [1, 2, 1] ধারণ করছে। রাম ১ বা ২ মুছে ফেলতে পারে। যদি রাম ১ মুছে ফেলে, তবে অ্যারে হবে [2,1], কারণ ১ XOR ২ = ৩। এখন স্যাম যেকোনো উপাদান মুছে ফেলতে পারে, কারণ রাম শেষ উপাদানটি মুছে ফেলবে এবং সে হারে যাবে। যদি রাম প্রথমে ২ মুছে ফেলে, তবে অ্যারে হবে [1,1], XOR হবে ০, তাই রাম হারে যাবে।
সমাধানের ধাপসমূহ
- n := nums.size()
- x := 0
- nums-এর প্রতিটি উপাদান 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
