C++-এ k এলিমেন্ট বাছাই করা যাতে ন্যূনতম দূরত্ব সর্বাধিক হয়

এই সমস্যাতে, একই রেখায় অবস্থিত n সংখ্যক পয়েন্টের একটি অ্যারে দেওয়া আছে। আমাদের কাজ হলো এই অ্যারেতে থেকে k সংখ্যক এলিমেন্ট এমনভাবে বাছাই করা যাতে তাদের মধ্যে ন্যূনতম দূরত্ব যতসম্ভব সর্বাধিক হয়।

উদাহরণ:

ইনপুট - array = {}

আউটপুট -

সমাধানের জন্য, আমাদের সর্বাধিক সম্ভাব্য ন্যূনতম দূরত্ব বের করতে হবে। এর জন্য প্রথমে অ্যারেটি সোর্ট করব এবং তারপর বাইনারি সার্চ চালিয়ে মিড পয়েন্টে সমাধান পাব।

উদাহরণ

সমাধানের প্রোগ্রাম:

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

bool canGenerateResult(int mid, int arr[], int n, int k) {
    int pos = arr[0];
    int elements = 1;
    for (int i = 1; i < n; i++) {
        if (arr[i] - pos >= mid) {
            pos = arr[i];
            elements++;
            if (elements == k)
                return true;
        }
    }
    return 0;
}

int maxMinDist(int arr[], int n, int k) {
    sort(arr, arr + n);
    int res = -1;
    int left = arr[0], right = arr[n-1];
    while (left < right) {
        int mid = (left + right) / 2;
        if (canGenerateResult(mid, arr, n, k)) {
            res = max(res, mid);
            left = mid + 1;
        } else
            right = mid;
    }
    return res;
}

int main() {
    int arr[] = {3, 5, 6, 9, 1, 8};
    int n = sizeof(arr)/sizeof(arr[0]);
    int k = 3;
    cout << "The maximized minimum distance is : " << maxMinDist(arr, n, k);
    return 0;
}

আউটপুট

The maximized minimum distance is : 4