এই সমস্যাতে, আমাদের একটি অ্যারে arr[] দেওয়া আছে যার সাইজ N এবং এতে 1 থেকে N পর্যন্ত মান আছে, কিন্তু একটি মান মিসিং। আমাদের কাজ হল সর্টেড অ্যারেতে একমাত্র মিসিং নাম্বার বের করা।
উদাহরণ দেখি:
ইনপুট
arr[] = {1, 2, 3, 5, 6, 7}
আউটপুট
4
সমাধানের পদ্ধতি
এই সমস্যা সমাধানের একটি সহজ পদ্ধতি হল সর্টেড অ্যারেটি লিনিয়ারলি ট্রাভার্স করা। এবং arr[i] = (i + 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
আরেকটি পদ্ধতি হল বাইনারি সার্চ ব্যবহার করা। মিড ইনডেক্সের ভ্যালু চেক করা। যদি মিডের ভ্যালু mid+1 হয় এবং (mid-1)-এর ভ্যালু mid হয়, তবে লেফট সাবঅ্যারে ট্রাভার্স করুন, অন্যথায় রাইট সাবঅ্যারে।
উদাহরণ ২
#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
