दोहराने वाले तत्व XOR ऑपरेटर की सरणी में दो गैर-दोहराने वाले तत्व खोजें?

Question

मान लीजिए कि मेरे पास 2 एन + 2 तत्वों के साथ एक सरणी है। सरणी में एन तत्व दो बार होते हैं और शेष दो तत्व अद्वितीय होते हैं। आपको ओ (एन) समय और ओ (1) अंतरिक्ष में इसे हल करना होगा। समाधान में से एक एक्सओआर का उपयोग कर रहा है। लेकिन मैं इसे समझने में सक्षम नहीं हूं। क्या कोई मुझे इसके बारे में मदद कर सकता है या मुझे बेहतर समाधान दे सकता है? समस्या और समाधान के

लिंक this

Answer 1

सबसे पहले है - ध्यान दें कि a xor a == 0, प्रत्येक a के लिए।

मान लें कि आपके पास दो अद्वितीय संख्याएं हैं - x,y।

यदि आप प्रत्येक तत्व पर xor करते हैं, तो आप एक ही संख्या के साथ समाप्त होते हैं, जो x xor y (क्योंकि प्रत्येक डुप्ली जोड़ी स्वयं को समाप्त कर देती है) के बराबर होती है, और कम से कम एक बिट "अप" होती है। इस बिट को चुनें (इससे कोई फर्क नहीं पड़ता कि आप कितना अधिक लेते हैं यदि एक और अधिक होता है), और सूची को दो उप सूचियों में विभाजित करें:
(1) इस संख्या को सेट करने वाली सभी संख्याएं।
(2) सभी संख्याएं जो इस बिट को अनसेट करती हैं।

अद्वितीय संख्याओं में से एक यह बिट है, दूसरा नहीं है (अन्यथा - यह पहली जगह "ऊपर" नहीं था), इसलिए आपके पास प्रत्येक सूची में एक अद्वितीय संख्या है।

प्रत्येक सूची को एक बार फिर से हटाएं, और सभी तत्वों पर xor करें, परिणाम इस सूची में अद्वितीय संख्या है, क्योंकि प्रत्येक डुप्लिकेट जोड़ी स्वयं को समाप्त कर देती है।