C++ প্রোগ্রাম: অ্যারে উপাদান যোগ করে সবগুলোকে k-এর চেয়ে বড় বা সমান করা

আমাদের একটি আনসর্টেড অ্যারে arr[] এবং একটি ইন্টিজার K আছে। আমাদের ন্যূনতম কত স্টেপে অ্যারে উপাদানগুলো যোগ করে সব উপাদান K-এর চেয়ে বড় বা সমান করা যায় তা বের করতে হবে। আমরা অ্যারের দুটি উপাদান যোগ করে একট बनाয় পারি।

উদাহরণ

Input: arr[] = {1, 10, 12, 9, 2, 3}, K = 6
Output: 2

ব্যাখ্যা

প্রথমে (1 + 2) যোগ করি, নতুন অ্যারে: 3, 10, 12, 9, 3। তারপর (3 + 3) যোগ করি, নতুন অ্যারে: 6, 10, 12, 9। এখন সব উপাদান ৬-এর চেয়ে বড় বা সমান। অতএব আউটপুট 2 অর্থাৎ ২ অপারেশন প্রয়োজন।

C++ প্রোগ্রাম উদাহরণ

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

class MinHeap {
    int *harr;
    int capacity;
    int heap_size;
    public:
    MinHeap(int *arr, int capacity);
    void heapify(int );
    int parent(int i) { return (i-1)/2; }
    int left(int i) { return (2*i + 1); }
    int right(int i) { return (2*i + 2); }
    int extractMin();
    int getMin() { return harr[0]; }
    int getSize() { return heap_size; }
    void insertKey(int k);
};

MinHeap::MinHeap(int arr[], int n) {
    heap_size = n;
    capacity = n;
    harr = new int[n];
    for (int i=0; i=0; i--)
        heapify(i);
}

void MinHeap::insertKey(int k) {
    heap_size++;
    int i = heap_size - 1;
    harr[i] = k;
    while (i != 0 && harr[parent(i)] > harr[i]) {
        swap(harr[i], harr[parent(i)]);
        i = parent(i);
    }
}

int MinHeap::extractMin() {
    if (heap_size <= 0)
        return INT_MAX;
    if (heap_size == 1) {
        heap_size--;
        return harr[0];
    }
    int root = harr[0];
    harr[0] = harr[heap_size-1];
    heap_size--;
    heapify(0);
    return root;
}

void MinHeap::heapify(int i) {
    int l = left(i);
    int r = right(i);
    int smallest = i;
    if (l < heap_size && harr[l] < harr[i])
        smallest = l;
    if (r < heap_size && harr[r] < harr[smallest])
        smallest = r;
    if (smallest != i) {
        swap(harr[i], harr[smallest]);
        heapify(smallest);
    }
}

int countMinOps(int arr[], int n, int k) {
    MinHeap h(arr, n);
    long int res = 0;
    while (h.getMin() < k) {
        if (h.getSize() == 1)
            return -1;
        int first = h.extractMin();
        int second = h.extractMin();
        h.insertKey(first + second);
        res++;
    }
    return res;
}

int main() {
    int arr[] = {1, 10, 12, 9, 2, 3};
    int n = sizeof(arr)/sizeof(arr[0]);
    int k = 6;
    cout << countMinOps(arr, n, k);
    return 0;
}