मान लीजिए हमारे पास nums नामक एक ऐरे है, जहां nums[i] चॉकबोर्ड पर लिखे गए हैं। राम और सैम बारी-बारी से चॉकबोर्ड से ठीक एक तत्व मिटाते हैं, राम पहले शुरू करता है। यदि किसी संख्या को मिटाने से चॉकबोर्ड के सभी तत्वों का बिटवाइज XOR 0 हो जाता है, तो वह खिलाड़ी हार जाता है। एक तत्व का बिटवाइज XOR वह तत्व स्वयं होता है, और शून्य तत्वों का बिटवाइज XOR 0 होता है। यदि कोई खिलाड़ी अपनी बारी चॉकबोर्ड के सभी तत्वों के बिटवाइज XOR 0 के साथ शुरू करता है, तो वह खिलाड़ी जीत जाएगा। मान लीजिए ऐरे [1, 2, 1] रखता है, तो राम 1 या 2 हटा सकता है, यदि राम 1 हटाता है, तो ऐरे [2,1] होगा, क्योंकि तत्वों का XOR 1 XOR 2 = 3 है, अब सैम कोई भी तत्व हटा सकता है, क्योंकि राम अंतिम तत्व मिटाएगा और वह हार जाएगा। यदि वह पहले 2 को हटाना चुनता है, तो ऐरे [1,1] हो जाता है, XOR 0 है, इसलिए राम हार जाएगा।
इसे हल करने के लिए, हम निम्न चरणों का पालन करेंगे -
- n := nums का आकार
- x := 0
- nums में सभी तत्वों i के लिए -
- x := x XOR i
- वापस करें 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