C++-এ দুটি সোর্টেড অ্যারেতে একস্ট্রা এলিমেন্টের ইনডেক্স বের করুন

দুটি সোর্টেড অ্যারে arr1 (সাইজ n) এবং arr2 (সাইজ n+1) দেওয়া আছে। arr2-এ arr1-এর সব এলিমেন্ট প্লাস একটি একস্ট্রা এলিমেন্ট আছে। একস্ট্রা এলিমেন্টটির ইনডেক্স (ইন arr2) বের করতে হবে।

উদাহরণ

arr1 = {3,5,7,8,9,12}

arr2 = {3,4,5,7,8,9,12}

একস্ট্রা এলিমেন্ট: 4 ইনডেক্স 1-এ → আউটপুট: 1

অ্যালগরিদম ১: লিনিয়ার সার্চ (O(n))

দুই অ্যারে প্যারালাললি ট্রাভার্স করুন। প্রথমে যেখানে arr1[i] != arr2[i], সেটিই একস্ট্রা।

C++ প্রোগ্রাম (লিনিয়ার)

#include <iostream>
using namespace std;

int findExtraElement(int arr1[], int arr2[], int n) {
    for (int i = 0; i < n; i++)
        if (arr1[i] != arr2[i]) break;
    return i;
}

int main() {
    int arr1[] = {3,5,7,8,9,12};
    int arr2[] = {3,4,5,7,8,9,12};
    int n = sizeof(arr1)/sizeof(arr1[0]);
    int idx = findExtraElement(arr1, arr2, n);
    cout << "The extra element is at index (" << idx << ") and the value is " << arr2[idx];
    return 0;
}

আউটপুট

The extra element is at index (1) and the value is 4

অ্যালগরিদম ২: বাইনারি সার্চ (O(log n))

সোর্টেড অ্যারে → বাইনারি সার্চ করুন।

• mid-এ arr1[mid] == arr2[mid] হলে একস্ট্রা ডানপাশে → low = mid+1।
• অন্যথায় বামপাশে → high = mid-1, ans = mid।

C++ প্রোগ্রাম (বাইনারি সার্চ)

int findExtraElement(int arr1[], int arr2[], int n) {
    int extraIndex = n; // ডিফল্ট: শেষে
    int low = 0, high = n - 1;
    while (low <= high) {
        int mid = (low + high) / 2;
        if (arr2[mid] == arr1[mid])
            low = mid + 1;
        else {
            extraIndex = mid;
            high = mid - 1;
        }
    }
    return extraIndex;
}

অ্যালগরিদম ৩: সম বিয়োগ (O(n), O(1) স্পেস)

sum(arr2) - sum(arr1) = extraValue। তারপর arr2-এ লিনিয়ার সার্চ করে ইনডেক্স খুঁজুন।

C++ প্রোগ্রাম (সম বিয়োগ)

int calcArraySum(int arr[], int n) {
    int sum = 0;
    for (int i = 0; i < n; i++) sum += arr[i];
    return sum;
}

int findExtraElement(int arr1[], int arr2[], int n) {
    int extraVal = calcArraySum(arr2, n+1) - calcArraySum(arr1, n);
    for (int i = 0; i <= n; i++)
        if (arr2[i] == extraVal) return i;
    return -1;
}

তুলনা