শাফল করা কপি অ্যারেতে অনুপস্থিত সংখ্যা খুঁজে বের করা C++-তে

মনে করুন, আমাদের দুটি অ্যারে 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