Tìm số bị thiếu trong một mảng khác được sao chép xáo trộn trong C ++

Giả sử, ta có hai mảng A và B, mảng A có n phần tử. Mảng thứ hai B có tất cả các phần tử của A, nhưng chúng bị xáo trộn và một phần tử bị loại bỏ. Chúng ta phải tìm ra những yếu tố còn thiếu. Vì vậy, nếu A =[4, 8, 1, 3, 7] và B =[7, 4, 3, 1], kết quả là 8.

Điều này có thể được giải quyết bằng thủ thuật XOR. Sự xuất hiện kết hợp của mỗi phần tử là hai lần, một lần ở A và một phần tử khác ở B, ngoại trừ một phần tử chỉ có một lần xuất hiện duy nhất ở A. Như chúng ta biết rằng x XOR x =0, vì vậy nếu chúng ta thực hiện XOR trong các phần tử của cả hai mảng. Kết quả sẽ bị thiếu số.

Ví dụ

#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);
}

Đầu ra

Missing element: 8