C++-এ একটি অ্যারেতে সব এলিমেন্ট পেয়ারের k-তম ছোট ডিফারেন্স বের করার প্রোগ্রাম

মান লিজिए আমাদের একটি লিস্ট দেওয়া আছে যাতে বেশ কিছু পূর্ণসংখ্যা রয়েছে। আমাদের অ্যারেতে প্রতিটি পেয়ারের ভ্যালুর ডিফারেন্স বের করতে হবে এবং k-তম ছোট ডিফারেন্স নম্বর বের করতে হবে। ইনডেক্স ০ থেকে শুরু হয় এবং k মান আমাদের ইনপুট হিসেবে দেওয়া থাকে।

তাই, যদি ইনপুট হয় numbers = {2, 6, 4, 8}, k = 2, তবে আউটপুট হবে 2।

পেয়ারগুলোর ডিফারেন্সগুলো হল:-

(2, 6) = 4

(2, 4) = 2

(2, 8) = 6

(6, 4) = 2

(6, 8) = 2

(4, 8) = 4

যদি আমরা ভ্যালুগুলো সর্ট করি, সেটি হয় 2, 2, 2, 4, 4, 6। ২-ন নাম্বার ছোট ভ্যালু হল 2। (ইনডেক্স ০ থেকে শুরু)।

এটি সমাধান করতে, আমরা এই ধাপগুলো ফলো করব:-

k কে ১ বাড়ান
ইনপুট অ্যারে সর্ট করুন
le := 0
ri := ইনপুটের লাস্ট এলিমেন্ট - ইনপুটের ফার্স্ট আইটেম
যতক্ষণ le < ri, করুন:-
- mid := (le + ri) / 2
- tmp := 0
- lp := 0
- i := 1 দিয়ে ইনিশিয়ালাইজ করুন, যখন i < ইনপুটের সাইজ, আপডেট করুন (i ১ বাড়িয়ে), করুন:-
  - যতক্ষণ input[i] - input[lp] > mid, করুন:-
    - lp := lp + 1
  - tmp := tmp + i - lp
- যদি tmp >= k, তবে -
  - ri := mid
- অন্যথায়
  - le := mid + 1
le রিটার্ন করুন

উদাহরণ

বेहतर বুঝতে নিচের ইমপ্লিমেন্টেশনটি দেখুন:-

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

int solve(vector<int>& input, int k) { 
    k++; 
    sort(input.begin(), input.end()); 
    int le = 0; 
    int ri = input.back() - input[0]; 
    while (le < ri) { 
        int mid = (le + ri) / 2; 
        long long tmp = 0; 
        int lp = 0; 
        for (int i = 1; i < input.size(); i++) { 
            while (input[i] - input[lp] > mid) lp++; 
            tmp += i - lp; 
        } 
        if (tmp >= k) ri = mid; 
        else le = mid + 1; 
    } 
    return le; 
} 

int main() { 
    vector<int> numbers = {2, 6, 4, 8}; 
    cout<< solve(numbers, 2) <<endl; 
    return 0; 
}

ইনপুট

vector<int> numbers = {2, 6, 4, 8}; cout<< solve(numbers, 2) <<endl;