N রেঞ্জ থেকে জেনারেটেড সিরিজে k-তম উপাদান বের করা (C++)

সমস্যা বিবরণ

Nটি রেঞ্জ [L, R] দেওয়া আছে। এই রেঞ্জগুলো মিলিয়ে একটি সিরিজ বানানো হয়। আমাদের কাজ হল সিরিজে k-তম উপাদান বের করা।

উদাহরণ

রেঞ্জ: {{1,3}, {5,7}}, k=4
সিরিজ: {1,2,3,5,6,7}
আউটপুট: 5

পদ্ধতি ১: সিরিজ তৈরি করে (O(total elements))

সব রেঞ্জের উপাদান একসাথে রাখে k-তমটি নেওয়া। মেমরি সমস্যা হতে পারে।

পদ্ধতি ২: বাইনারি সার্চ + প্রিফিক্স কাউন্ট (O(N log Max)) - সেরা

প্রতিটি রেঞ্জ পর্যন্ত মোট উপাদান সংখ্যা প্রিফিক্স অ্যারেতে রাখা। বাইনারি সার্চ দিয়ে k থাকা রেঞ্জ খুঁজে সেটার মধ্যে k-তম মান বের করা।

#include <iostream>
using namespace std;

int findKth(int n, int k, int range[][2]) {
    vector<int> pref(n+1,0);
    for(int i=0;i=k){ idx=mid; hi=mid-1; }
        else lo=mid+1;
    }
    int L=range[idx-1][0], R=range[idx-1][1];
    int pos = k - pref[idx-1];
    return L + pos - 1;
}

int main() {
    int range[][2]={{1,3},{5,8}};
    cout << findKth(2,4,range); // 5
    return 0;
}