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, हम जान सकते हैं कि सूची के सभी तत्व 6 से बड़े हैं। इसलिए आउटपुट 2 है यानी इसे करने के लिए 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; 
}