หาตัวเลขที่หายไปในอีกอาร์เรย์หนึ่งซึ่งเป็นสำเนาที่สับเปลี่ยนใน C++

สมมติว่ามีอาร์เรย์สองอาร์เรย์ A และ B อาร์เรย์ A มี n องค์ประกอบ อาร์เรย์ที่สอง B มีองค์ประกอบทั้งหมดของ A แต่ถูกสับเปลี่ยน (Shuffled) และเอาออกไปหนึ่งองค์ประกอบ เราต้องหาองค์ประกอบที่หายไป ดังนั้นถ้า 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