পরিসীমায় অনুপস্থিত এলিমেন্ট খুঁজে বের করা C++-এ

এই সমস্যায়, আমাদের একটি অ্যারে arr[] দেওয়া আছে যার আকার n এবং শুরু ও শেষ এলিমেন্ট দিয়ে পরিসীমা নির্দেশ করা আছে। আমাদের কাজ হল পরিসীমার অনুপস্থিত এলিমেন্ট খুঁজে বের করা।

সমস্যা বর্ণনা - আমরা পরিসীমার সেই এলিমেন্টগুলো বের করব جو অ্যারেতে নেই।

উদাহরণ

ইনপুট

arr[] = {4, 6, 3, 7}, start = 3, end = 8

আউটপুট

5, 8

ব্যাখ্যা

পরিসীমা: [3, 4, 5, 6, 7, 8]

অ্যারে: {4, 6, 3, 7}

পরিসীমার যেসব এলিমেন্ট অ্যারেতে নেই: 5, 8

সমাধানের পদ্ধতি

এই সমস্যাটি একাধিকভাবে সমাধান করা যায়:

পদ্ধতি ১: সর্টিং ও লোয়ার বাউন্ড

একটি সহজ সমাধান হল পরিসীমার সব এলিমেন্ট সরাসরি অ্যারেতে চেক করা। এর জন্য অ্যারেটি সর্ট করুন এবং পরিসীমার প্রথম এলিমেন্টটি অ্যারেতে খুঁজে বের করুন (lower_bound) এবং তারপর অনুপস্থিত এলিমেন্টগুলো প্রিন্ট করুন।

প্রোগ্রাম উদাহরণ (পদ্ধতি ১)

#include <bits/stdc++.h>
using namespace std;

void findMissingElements(int arr[], int n, int low, int high) {
    sort(arr, arr + n);
    int* pointerVal = lower_bound(arr, arr + n, low);
    int index = pointerVal - arr;
    int i = index, x = low;
    
    while (i < n && x <= high) {
        if (arr[i] != x)
            cout << x << " ";
        else
            i++;
        x++;
    }
    
    while (x <= high)
        cout << x++ << " ";
}

int main() {
    int arr[] = { 4, 6, 3, 7 };
    int n = sizeof(arr) / sizeof(arr[0]);
    int low = 3, high = 9;
    cout << "The missing elements are ";
    findMissingElements(arr, n, low, high);
    return 0;
}

আউটপুট

The missing elements are 5 8 9

পদ্ধতি ২: বুলিয়ান অ্যারে ব্যবহার

একটি অন্য পদ্ধতিতে বুলিয়ান অ্যারে ব্যবহার করা হয়। আমরা (end - start + 1) আকারের একটি বুলিয়ান অ্যারে তৈরি করব। এই অ্যারের প্রতিটি এলিমেন্টের জন্য চেক করব (i+start) অ্যারেতে আছে কিনা। যদি থাকে, boolArray[i] = true করব, নয় তবে false। শেষে বুলিয়ান অ্যারে ট্রাভার্স করে false যেগুলো তাদের পরিসীমার মান প্রিন্ট করব।

প্রোগ্রাম উদাহরণ (পদ্ধতি ২)

#include <bits/stdc++.h>
using namespace std;

void findMissingElements(int arr[], int n, int start, int end) {
    bool boolArray[end - start + 1] = { false };
    
    for (int i = 0; i < n; i++) {
        if (start <= arr[i] && arr[i] <= end)
            boolArray[arr[i] - start] = true;
    }
    
    for (int i = 0; i <= end - start; i++) {
        if (boolArray[i] == false)
            cout << (start + i) << "\t";
    }
}

int main() {
    int arr[] = { 4, 6, 3, 7 };
    int n = sizeof(arr) / sizeof(arr[0]);
    int low = 3, high = 9;
    cout << "The missing elements are ";
    findMissingElements(arr, n, low, high);
    return 0;
}

আউটপুট

The missing elements are 5 8 9

পদ্ধতি ৩: হ্যাশ টেবিল ব্যবহার

একটি অন্য পদ্ধতিতে হ্যাশ টেবিল ব্যবহার করা হয়। অ্যারের সব এলিমেন্ট হ্যাশ টেবিলে ইনসার্ট করুন এবং পরিসীমা ট্রাভার্স করে যেসব এলিমেন্ট হ্যাশ টেবিলে নেই সেগুলো প্রিন্ট করুন।

প্রোগ্রাম উদাহরণ (পদ্ধতি ৩)

#include <bits/stdc++.h>
using namespace std;

void findMissingElements(int arr[], int n, int start, int end) {
    unordered_set<int> arrEle;
    for (int i = 0; i < n; i++)
        arrEle.insert(arr[i]);
    
    for (int i = start; i <= end; i++)
        if (arrEle.find(i) == arrEle.end())
            cout << i << "\t";
}

int main() {
    int arr[] = { 4, 6, 3, 7 };
    int n = sizeof(arr) / sizeof(arr[0]);
    int low = 3, high = 9;
    cout << "The missing elements are ";
    findMissingElements(arr, n, low, high);
    return 0;
}

আউটপুট

The missing elements are 5 8 9