मान लीजिए, हमारे पास दो सरणियाँ A और B हैं, सरणी A में n तत्व हैं। दूसरी सरणी बी में ए के सभी तत्व हैं, लेकिन उन्हें फेरबदल किया जाता है और एक तत्व हटा दिया जाता है। हमें लापता तत्वों को खोजना होगा। तो अगर ए =[4, 8, 1, 3, 7], और बी =[7, 4, 3, 1], आउटपुट 8 है।
इसे XOR ट्रिक का उपयोग करके हल किया जा सकता है। प्रत्येक तत्व की संयुक्त घटना दो बार होती है, एक ए में और दूसरा बी में, एक तत्व को छोड़कर जिसमें ए में केवल एक ही घटना होती है। जैसा कि हम जानते हैं कि एक्स एक्सओआर एक्स =0, इसलिए यदि हम दोनों के तत्वों में एक्सओआर करते हैं सरणियाँ। परिणाम में नंबर नहीं होगा।
उदाहरण
#include<iostream>
using namespace std;
int FindMissingElement(int A[], int B[], int n) {
int min_element = 0;
for (int i = 0; i < n; i++)
min_element = min_element ^ A[i];
for (int i = 0; i < n - 1; i++)
min_element = min_element ^ B[i];
return min_element;
}
int main() {
int A[] = {4, 8, 1, 3, 7};
int B[] = {7, 4, 3, 1};
int n = sizeof(A) / sizeof(A[0]);
cout << "Missing element: " << FindMissingElement(A, B, n);
} आउटपुट
Missing element: 8
