আমাদের কাছে সাজানো না হওয়া এলিমেন্টের অ্যারে আছে যেমন arr[] এবং একটি পূর্ণসংখ্যা 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 , আমরা জানতে পারি যে তালিকার সমস্ত উপাদান 6 এর থেকে বড় . তাই আউটপুট হল
2 i:e 2 এটি করার জন্য অপারেশন প্রয়োজন।
উদাহরণ
#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<n; i++)
harr[i] = arr[i];
for (int i=n/2-1; 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;
} আউটপুট
2
