এই সমস্যায়, আমাদের n আকারের একটি arr[] দেওয়া হয়। আমাদের কাজ হল একটি অনুপস্থিত নম্বর পরিসরে খুঁজে পাওয়া .
অ্যারেতে ক্ষুদ্রতম মান থেকে (smallest + n) পর্যন্ত সমস্ত মান থাকে। পরিসরের একটি উপাদান অ্যারে থেকে অনুপস্থিত। এবং আমাদের এই অনুপস্থিত মান খুঁজে বের করতে হবে।
সমস্যাটি বোঝার জন্য একটি উদাহরণ নেওয়া যাক,
ইনপুট
arr[] = {4, 8, 5, 7} আউটপুট
6
সমাধান পদ্ধতি
সমস্যার একটি সহজ সমাধান হল অ্যারে সাজানোর মাধ্যমে অনুপস্থিত উপাদানটি অনুসন্ধান করা এবং তারপর সর্বনিম্ন মান থেকে শুরু হওয়া পরিসরের প্রথম উপাদানটি সন্ধান করা যা অ্যারেতে উপস্থিত নয় তবে পরিসরে উপস্থিত রয়েছে৷
এই সমাধানটি একটি নিষ্পাপ পদ্ধতি এবং সমস্যার সমাধান করবে O(n log n) সময়ের জটিলতা৷
কম সময়ে সমস্যা সমাধানের আরেকটি পদ্ধতি হল অ্যারের মান এবং পরিসরের XOR ব্যবহার করা। আমরা রেঞ্জের সমস্ত মানের XOR খুঁজে পাব এবং অ্যারের সমস্ত মানের XORও খুঁজে পাব। এই উভয় মানের XOR হবে আমাদের অনুপস্থিত মান।
উদাহরণ
আমাদের সমাধানের কাজ চিত্রিত করার জন্য প্রোগ্রাম
#include <bits/stdc++.h>
using namespace std;
int findMissingNumArr(int arr[], int n){
int arrMin = *min_element(arr, arr+n);
int numXor = 0;
int rangeXor = arrMin;
for (int i = 0; i < n; i++) {
numXor ^= arr[i];
arrMin++;
rangeXor ^= arrMin;
}
return numXor ^ rangeXor;
}
int main(){
int arr[] = { 5, 7, 4, 8, 9};
int n = sizeof(arr)/sizeof(arr[0]);
cout<<"The missing value in the array is "<<findMissingNumArr(arr, n);
return 0;
} আউটপুট
The missing value in the array is 6
