জ্যামিতিক অনুক্রমে অনুপস্থিত সংখ্যা খুঁজে বের করা C++-তে

মনে করুন আমাদের একটি অ্যারে আছে যা জ্যামিতিক অনুক্রমের উপাদানগুলো ক্রমানুসারে উপস্থাপন করে। একটি উপাদান অনুপস্থিত। আমাদের অনুপস্থিত উপাদানটি বের করতে হবে। তাই যদি arr = [1, 3, 27, 81], আউটপুট হবে 9, কারণ 9 অনুপস্থিত।

বাইনারি সার্চ ব্যবহার করে এই সমস্যাটি সমাধান করা যায়। আমরা মধ্যবর্তী উপাদানে যাব, তারপর চেক করব মধ্যবর্তী এবং তার পরবর্তী উপাদানের অনুপাত সাধারণ অনুপাতের সমান কিনা। যদি না হয়, তবে অনুপস্থিত উপাদান mid এবং mid+1 ইনডেক্সের মাঝপথে আছে। যদি মধ্যবর্তী উপাদান GP-এ n/2তম উপাদান হয়, তবে অনুপস্থিত উপাদান ডান পাশে আছে, অন্যথায় বাম পাশে।

উদাহরণ

#include <iostream>
#include <cmath>
using namespace std;

class Progression {
public:
    int missingUtil(int arr[], int left, int right, int ratio) {
        if (right <= left)
            return INT_MAX;
        int mid = left + (right - left) / 2;
        if (arr[mid + 1] - arr[mid] != ratio)
            return (arr[mid] * ratio);
        if (mid > 0 && arr[mid] / arr[mid - 1] != ratio)
            return (arr[mid - 1] * ratio);
        if (arr[mid] == arr[0] * pow(ratio, mid))
            return missingUtil(arr, mid + 1, right, ratio);
        return missingUtil(arr, left, mid - 1, ratio);
    }
    int missingElement(int arr[], int n) {
        int ratio = pow(arr[n - 1] / arr[0], 1.0 / n);
        return missingUtil(arr, 0, n - 1, ratio);
    }
};

int main() {
    Progression pg;
    int arr[] = {1, 3, 27, 81};
    int n = sizeof(arr) / sizeof(arr[0]);
    cout << "The missing element is: " << pg.missingElement(arr, n);
}

আউটপুট

The missing element is: 9