C++ में 2n+1 पूर्णांक तत्वों की एक सरणी में एकल खोजें

इस समस्या में, हमें एक सरणी दी जाती है जिसमें (2n+ 1) पूर्णांक मान होते हैं। इन सभी मानों में से, n तत्व सरणी में दो बार दिखाई देते हैं और सरणी में केवल एक तत्व होता है जो एक बार दिखाई देता है। हमारा काम 2n+1 पूर्णांक तत्वों की सरणी में एकल खोजना है।

समस्या को समझने के लिए एक उदाहरण लेते हैं,

इनपुट

arr[] = {1, 3, 5, 6, 5, 1, 3}

आउटपुट

5

समाधान दृष्टिकोण

समस्या का एक सरल समाधान तत्वों के लिए एक काउंटर का उपयोग करना है। यदि कोई तत्व सामने आता है, तो उसके मूल्य और घटना की संख्या को संग्रहीत करें। इसके बाद तालिका में उस तत्व की खोज करें जिसमें घटना संख्या =1 है। एक अधिक कुशल समाधान एक्सओआर का उपयोग करेगा। यहां, हम सरणी के सभी तत्वों का XOR प्रदर्शन करेंगे। यह एक्सओआर सभी तत्वों को डबल आवृत्ति 0 के साथ बना देगा। और एकमात्र तत्व जिसका मूल्य मौजूद होगा वह है जिसकी घटना 1 है।

यह XOR के गुणों के कारण है जो −

- a^a = 0
- a^0 = a

हमारे समाधान की कार्यप्रणाली को दर्शाने वाला कार्यक्रम,

उदाहरण

#include <iostream>
using namespace std;
int findSingleValue(int arr[], int n) {
   int element = 0;
   for (int i = 0; i < n; i++)
      element = element ^ arr[i];
   return element;
}
int main() {
   int arr[] = { 1, 3, 5, 6, 5, 1, 3 };
   int n = sizeof(arr) / sizeof(arr[0]);
   cout<<"The element of the array with single occurrence is "<<findSingleValue(arr, n);
   return 0;
}

आउटपुट

The element of the array with single occurrence is 6