ধারণা
n স্বতন্ত্র পূর্ণসংখ্যার একটি প্রদত্ত অ্যারে অ্যারে[] এর সাপেক্ষে, উপাদানগুলি অনুপস্থিত একটি উপাদানের সাথে ক্রমানুসারে ইনসেন্ডিং ক্রমে স্থাপন করা হয়। আমাদের কাজ হল অনুপস্থিত উপাদান নির্ধারণ করা।
ইনপুট
array[] = {1, 2, 3, 4, 5, 6, 7, 9} আউটপুট
8
ইনপুট
array[] = {-4, -2, -1, 0, 1, 2} আউটপুট
-3
ইনপুট
array[] = {1, 2, 3, 4} আউটপুট
-1
কোন উপাদান অনুপস্থিত.
পদ্ধতি
নীতি
-
অসামঞ্জস্যের জন্য দেখুন:এই নীতি অনুসারে, প্রতিটি উপাদানের জন্য যেকোনো উপাদান এবং এর সূচকের মধ্যে পার্থক্য অবশ্যই অ্যারে[0] হতে হবে।
উদাহরণ,
A[] ={1, 2, 3, 4, 5} -> সামঞ্জস্যপূর্ণ
B[] ={201, 202, 203, 204} -> সামঞ্জস্যপূর্ণ
C[] ={1, 2, 3, 5, 6} -> C[3] – 3 হিসাবে অসামঞ্জস্যপূর্ণ!=C[0] অর্থাৎ 5 – 3 !=1
-
অসঙ্গতি নির্ধারণ করা O(logN) এ প্রতিবার অ্যারের অর্ধেক স্ক্যান করতে সাহায্য করে।
অ্যালগরিদম
-
মধ্যম উপাদান নির্ধারণ করুন এবং এটি সামঞ্জস্যপূর্ণ কিনা তা যাচাই করুন।
-
যদি মধ্যম উপাদানটি সামঞ্জস্যপূর্ণ হয়, তাহলে যাচাই করুন যে মধ্যম উপাদান এবং এর পরবর্তী উপাদানের মধ্যে পার্থক্য 1-এর চেয়ে বেশি যেমন অ্যারে [মিড + 1] – অ্যারে[মিড]> 1
-
যদি হ্যাঁ, তাহলে অ্যারে[মিড] + 1 অনুপস্থিত উপাদান।
-
অন্যথায়, আমাদের মধ্যম উপাদান থেকে ডান অর্ধেক অ্যারে স্ক্যান করতে হবে এবং ধাপ-1-এ যেতে হবে।
-
-
যদি মধ্যম উপাদান অসামঞ্জস্যপূর্ণ হয়, তবে মধ্যম উপাদান এবং এর পূর্ববর্তী উপাদানের মধ্যে পার্থক্য 1-এর বেশি হলে যাচাই করুন অর্থাৎ অ্যারে[মিড] – অ্যারে[মধ্য – 1]> 1
-
যদি হ্যাঁ, তাহলে অ্যারে[মিড] – 1 হল অনুপস্থিত উপাদান।
-
অন্যথায়, আমাদের মধ্যম উপাদান থেকে বাম অর্ধেক অ্যারে স্ক্যান করতে হবে এবং ধাপ-1-এ যেতে হবে।
-
উদাহরণ
// CPP implementation of the approach
#include<bits/stdc++.h>
using namespace std;
// Shows function to return the missing element
int findMissing(int array[], int n1){
int low = 0, high = n1 - 1;
int mid1;
while (high > low){
mid1 = low + (high - low) / 2;
// Verify if middle element is consistent
if (array[mid1] - mid1 == array[0]){
// Here, no inconsistency till middle elements
// When missing element is just after
// the middle element
if (array[mid1 + 1] - array[mid1] > 1)
return array[mid1] + 1;
else{
// Go right
low = mid1 + 1;
}
}
else{
// Here inconsistency found
// When missing element is just before
// the middle element
if (array[mid1] - array[mid1 - 1] > 1)
return array[mid1] - 1;
else{
// Go left
high = mid1 - 1;
}
}
}
// Here, no missing element found
return -1;
}
// Driver code
int main(){
int array[] = { -9, -8, -6, -5, -4, -3, -2, -1, 0 };
int n1 = sizeof(array)/sizeof(array[0]);
cout <<"The Missing Element:" <<(findMissing(array, n1));
} আউটপুট
The Missing Element:-7
