মান लीজিয়ে একটি অ্যারে আছে যা আর্থিক প্রগতির (arithmetic progression) উপাদানগুলো ক্রম অনুযায়ী উপস্থাপন করে। একটি উপাদান অনুপস্থিত। আমাদের কাজ হলো অনুপস্থিত উপাদানটি বের করা। তাই যদি arr = [2, 4, 8, 10, 12, 14] হয়, তবে আউটপুট হবে 6, কারণ 6 অনুপস্থিত।
বাইনারি সার্চ ব্যবহার করে এই সমস্যা সমাধান করা যায়। আমরা মিডেল এলিমেন্টে যাব, তারপর যাচাই করব মিডেল এবং এর পরবর্তী উপাদানের পার্থক্য diff-এর সমান কিনা। যদি না হয়, তবে অনুপস্থিত উপাদান mid এবং mid + 1 ইনডেক্সের মধ্যে রয়েছে। যদি মিডেল উপাদান AP-র n/2তম উপাদান হয়, তবে অনুপস্থিত উপাদান ডান পাশে থাকবে, অন্যথায় বাম পাশে।
উদাহরণ (C++)
#include <iostream> using namespace std; #define INT_MAX 999999 class Progression { public: int missingUtil(int arr[], int left, int right, int diff) { if (right <= left) return INT_MAX; int mid = left + (right - left) / 2; if (arr[mid + 1] - arr[mid] != diff) return (arr[mid] + diff); if (mid > 0 && arr[mid] - arr[mid - 1] != diff) return (arr[mid - 1] + diff); if (arr[mid] == arr[0] + mid * diff) return missingUtil(arr, mid + 1, right, diff); return missingUtil(arr, left, mid - 1, diff); } int missingElement(int arr[], int n) { int diff = (arr[n - 1] - arr[0]) / n; return missingUtil(arr, 0, n - 1, diff); } }; int main() { Progression pg; int arr[] = {2, 4, 8, 10, 12, 14}; int n = sizeof(arr) / sizeof(arr[0]); cout << "The missing element is: " << pg.missingElement(arr, n)<<endl; }ইনপুট
[2,4,8,10,12,14]
আউটপুট
The missing element is: 6
