हमारे पास अवर्गीकृत तत्वों की सरणी है अर्थात 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