এই সমস্যায়, আমাদেরকে একটি arr[] সাইজের N দেওয়া হয়েছে যেখানে 1 থেকে N পর্যন্ত মান রয়েছে এবং অ্যারেতে একটি মান নেই। আমাদের কাজ হল একটি সাজানো অ্যারেতে একমাত্র অনুপস্থিত নম্বর খুঁজে পাওয়া .
সমস্যাটি বোঝার জন্য একটি উদাহরণ নেওয়া যাক,
ইনপুট
arr[] = {1, 2, 3, 5, 6, 7} আউটপুট
4
সমাধান পদ্ধতি
রৈখিকভাবে সাজানো অ্যারে অতিক্রম করে সমস্যার একটি সহজ সমাধান। এবং তারপর arr[i] =(i + 1) ব্যবহার করে অনুপস্থিত মান পরীক্ষা করুন।
উদাহরণ 1
আমাদের সমাধানের কাজ চিত্রিত করার জন্য প্রোগ্রাম
#include <iostream>
using namespace std;
int findMissingValArray(int arr[], int N){
for(int i = 0; i < N; i++){
if(arr[i] != (i+1))
return (i+1);
}
return -1;
}
int main(){
int arr[] = {1, 2, 3, 4, 6};
int N = sizeof(arr)/sizeof(arr[0]);
cout<<"The missing value from the array is "<<findMissingValArray(arr, N);
return 0;
} আউটপুট
The missing value from the array is 5
সমস্যা সমাধানের আরেকটি পদ্ধতি হল বাইনারি অনুসন্ধান ব্যবহার করা এবং মাঝখানে মান পরীক্ষা করা। যদি মাঝামাঝি মানটি মধ্য+1 হয় এবং (মধ্য - 1) এর মান (মধ্য) হয়, তাহলে আমরা বাম সাব্যারে অতিক্রম করব এবং বিপরীতে যাব।
উদাহরণ 2
আমাদের সমাধানের কাজ চিত্রিত করার জন্য প্রোগ্রাম
#include <iostream>
using namespace std;
int findMissingValArray(int arr[], int N){
int s = 0, e = N - 1;
while (s <= e) {
int mid = (s + e) / 2;
if (arr[mid] != mid + 1 && arr[mid - 1] == mid)
return (mid + 1);
if (arr[mid] != (mid + 1))
e = (mid - 1);
else
s = (mid + 1);
}
return -1;
}
int main(){
int arr[] = {1, 2, 3, 4, 6};
int N = sizeof(arr)/sizeof(arr[0]);
cout<<"The missing value from the array is "<<findMissingValArray(arr, N);
return 0;
} আউটপুট
The missing value from the array is 5
