এই সমস্যায়, আমাদেরকে n আকারের একটি অ্যারে অ্যারে [] দেওয়া হয়েছে এবং সূচনা এবং পরিসীমা নির্দেশ করে। আমাদের কাজ হল একটি পরিসরের অনুপস্থিত উপাদানগুলি খুঁজে বের করা৷
৷সমস্যা বর্ণনা − আমরা পরিসরের উপাদানগুলি খুঁজে পাব যেগুলি পরিসরে উপস্থিত নয়৷
সমস্যাটি বোঝার জন্য একটি উদাহরণ নেওয়া যাক,
ইনপুট
arr[] = {4, 6, 3, 7}, start = 3, end = 8 আউটপুট
5, 8
ব্যাখ্যা
পরিসীমা হল [3, 4, 5, 6, 7, 8]
অ্যারে হল {4, 6, 3, 7}
পরিসরের উপাদান যা অ্যারেতে নেই তা হল 5, 8
সমাধান পদ্ধতি
আপনি একাধিক উপায়ে এই সমস্যার সমাধান করতে পারেন। তারা হল,
#পন্থা 1
একটি সহজ সমাধান পদ্ধতি হল সরাসরি অ্যারের মধ্যে পরিসরের সমস্ত উপাদান পরীক্ষা করে। এর জন্য, আমরা অ্যারে সাজাব এবং তারপর অ্যারের মধ্যে রেঞ্জের প্রথম উপাদানটি খুঁজে বের করব এবং তারপরে অনুপস্থিত উপাদানগুলি খুঁজে বের করে প্রিন্ট করব।
আমাদের সমাধানের কাজ চিত্রিত করার জন্য প্রোগ্রাম,
উদাহরণ
#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
#অ্যাপ্রোচ 2
সমস্যা সমাধানের আরেকটি পদ্ধতি হল একটি অ্যারে ব্যবহার করা। আমরা আকারের একটি বুলিয়ান অ্যারে তৈরি করব (শেষ - শুরু)। এই অ্যারের প্রতিটি উপাদানের জন্য, আমরা অ্যারেতে (i+start) উপস্থিত আছে কিনা তা খুঁজে পাব। যদি এটি উপস্থিত থাকে, মার্ক arr[i] =true অন্যথায় মার্ক arr[i] =মিথ্যা। শেষে, আমরা বুলিয়ান অ্যারে অতিক্রম করব এবং মিথ্যা হিসাবে চিহ্নিত সমস্ত উপাদান প্রিন্ট করব।
আমাদের সমাধানের কাজ চিত্রিত করার জন্য প্রোগ্রাম,
উদাহরণ
#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
#অ্যাপ্রোচ 3
সমস্যা সমাধানের আরেকটি পদ্ধতি হল হ্যাশ টেবিল ব্যবহার করা। একটি হ্যাশ টেবিলে অ্যারের সমস্ত উপাদান সন্নিবেশ করান এবং সন্নিবেশ করার পরে রেঞ্জটি অতিক্রম করুন এবং পরিসরে উপস্থিত নয় এমন সমস্ত উপাদান প্রিন্ট করুন৷
আমাদের সমাধানের কাজ চিত্রিত করার জন্য প্রোগ্রাম,
উদাহরণ
#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
