অ্যারে − একই ডেটা টাইপের এলিমেন্টগুলোর একটি কন্টেইনার, যেগুলো ০-ইন্ডেক্সড।
এই সমস্যাটিতে, আমরা একটি ইন্টিজার অ্যারে ব্যবহার করব। এবং চেক করব সব এলিমেন্ট কি দেওয়া সংখ্যা k-এর চেয়ে বড় বা সমান। যদি না হয়, তবে অ্যারের দুটি ন্যূনতম এলিমেন্ট যোগ করে সেটিকে একক এলিমেন্ট হিসেবে বিবেচনা করব। তারপর নতুন অ্যারেতে আবার সেই কন্ডিশন চেক করব। যদি কন্ডিশন পূরণ হয়, তবে যোগ করা হয়েছে কতবার তা রিটার্ন করব।
অ্যারে = { 2, 6, 3, 12, 7 } K = 5 আউটপুট: 1
ব্যাখ্যা − প্রথমে চেক করব সব এলিমেন্ট k-এর চেয়ে বড় বা সমান কিনা। যেহেতু সেটি পূরণ হয় না, তাই দুটি ন্যূনতম সংখ্যা (২ এবং ৩) যোগ করব। নতুন অ্যারেতে প্রথম এলিমেন্ট হবে ৫। আবার চেক করলে কন্ডিশন পূরণ হয়, তাই যোগ করার সংখ্যা রিটার্ন করব।
অ্যালগরিদম
ইনপুট − অ্যারে এবং K
স্টেপ ১: চেক করুন সব এলিমেন্ট কি K-এর চেয়ে বড় বা সমান
স্টেপ ২: যদি (হ্যাঁ) { যোগ করার সংখ্যা প্রিন্ট করুন } exit(0)
স্টেপ ৩: অন্যথায় { অ্যারের দুটি ন্যূনতম এলিমেন্ট যোগ করে একক এলিমেন্ট বানান }
স্টেপ ৪: স্টেপ ১-এ যান
উদাহরণ
#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 main(){ int arr[] = { 2, 6,3,12, 7}; int n = sizeof(arr)/sizeof(arr[0]); int k = 5; 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++; } cout << res; return 0; }
আউটপুট
1
