मान लीजिए, हमारे पास दो ऐरे A और B हैं, ऐरे A में n तत्व हैं। दूसरा ऐरे B में A के सभी तत्व हैं, लेकिन वे शफल हैं और एक तत्व हटा दिया गया है। हमें लापता तत्व खोजना है। तो यदि A = [4, 8, 1, 3, 7], और B = [7, 4, 3, 1], आउटपुट 8 है।
इसे XOR ट्रिक का उपयोग करके हल किया जा सकता है। प्रत्येक तत्व की संयुक्त घटना दो बार होती है, एक A में, और दूसरी B में, एक तत्व को छोड़कर जिसकी केवल A में एकल घटना होती है। चूंकि हम जानते हैं कि x XOR x = 0, इसलिए यदि हम दोनों ऐरे के तत्वों में XOR करते हैं। परिणाम लापता संख्या होगी।
उदाहरण
#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
