สมมติว่าเรามีอาร์เรย์ 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
