সোর্টেড অ্যারেতে অনুপস্থিত এলিমেন্ট (Missing Element) খুঁজে বের করা (C++)

এই সমস্যায় একটি সোর্টেড ইউনিক অ্যারে A দেওয়া আছে। বাম থেকে k-তম অনুপস্থিত সংখ্যা বের করতে হবে।

উদাহরণ

ইনপুট: [4,7,9,10], k = 1

আউটপুট: 5

বাইনারি সার্চ সমাধান

অ্যারেটে অনুপস্থিত সংখ্যা কাউন্ট করার ফর্মুলা: missing(i) = nums[i] - nums[0] - i। বাইনারি সার্চ দিয়ে সঠিক পজিশন খুঁজুন।

C++ প্রোগ্রাম

#include <bits/stdc++.h>
using namespace std;

class Solution {
public:
    int missingElement(vector<int>& nums, int k) {
        int n = nums.size();
        int low = 0, high = n - 1;

        // শেষ এলিমেন্টের পরের অনুপস্থিত সংখ্যা
        if (nums[n-1] - nums[0] + 1 - n < k)
            return nums[n-1] + (k - (nums[n-1] - nums[0] + 1 - n));

        while (low < high - 1) {
            int mid = low + (high - low) / 2;
            int present = mid - low + 1;
            int absent = nums[mid] - nums[low] + 1 - present;
            if (absent >= k) high = mid;
            else { k -= absent; low = mid; }
        }
        return nums[low] + k;
    }
};

int main() {
    vector<int> v = {4, 7, 9, 10};
    Solution ob;
    cout << ob.missingElement(v, 1);
    return 0;
}