इस समस्या में, हमें (2n + 1) पूर्णांक मानों से युक्त एक सरणी दी गई है। इन सभी मानों में से, n तत्व सरणी में दो बार प्रकट होते हैं और सरणी में केवल एक तत्व है जो एक बार प्रकट होता है। हमारा कार्य 2n+1 पूर्णांक तत्वों की सरणी में एकल तत्व खोजना है।
आइए एक उदाहरण से इस समस्या को समझते हैं,
इनपुट
arr[] = {1, 3, 5, 6, 5, 1, 3}आउटपुट
5
समाधान दृष्टिकोण
इस समस्या का एक सरल समाधान तत्वों के लिए एक काउंटर का उपयोग करना है। यदि कोई तत्व मिलता है, तो उसका मान और घटना काउंट स्टोर करें। इसके बाद उस तत्व को टेबल में खोजें जिसका घटना काउंट = 1 है। एक अधिक कुशल समाधान XOR का उपयोग करना होगा। यहां, हम सरणी के सभी तत्वों का XOR करेंगे। यह 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
