C++ में सरणी के तत्वों को तब तक जोड़ना जब तक प्रत्येक तत्व k से बड़ा या बराबर न हो जाए

सरणी (Array) - एक सरणी एक ही डेटा प्रकार के तत्वों का एक कंटेनर है, जिसके तत्व 0 अनुक्रमित होते हैं।

इस समस्या में, हम पूर्णांकों की एक सरणी का उपयोग करेंगे। और जांचेंगे कि क्या सभी तत्व दी गई संख्या से बड़े हैं या नहीं। यहां हम जांचेंगे कि सरणी के सभी तत्व दी गई संख्या k से बड़े या बराबर हैं या नहीं। यदि नहीं, तो हम सरणी के दो न्यूनतम तत्वों को जोड़ेंगे और इस योग को एक तत्व मानेंगे। और फिर नई सरणी के लिए समान शर्त की जांच करेंगे। यदि शर्त पूरी होती है तो योग किए जाने की संख्या वापस कर दी जाती है।

Array = { 2, 6,3,12, 7} K = 5 Output : 1

व्याख्या - पहले हम जांचेंगे कि क्या सभी तत्व k से बड़े या बराबर हैं। चूंकि वे नहीं हैं, हम दो न्यूनतम संख्याओं को जोड़ेंगे। जो 2 और 3 हैं, इसलिए हमारी नई सरणी में पहला तत्व 5 होगा। अब, फिर से जांचेंगे, इस बार शर्त पूरी हो गई है इसलिए हम किए गए जोड़ों की संख्या वापस कर देंगे।

एल्गोरिदम

इनपुट - सरणी और K

चरण 1: जांचें कि क्या सभी तत्व K से बड़े या बराबर हैं चरण 2: यदि (हां) {    पुनरावृत्तियों की संख्या प्रिंट करें। } exit(0) चरण 3: अन्यथा {    सरणी के दो सबसे छोटे तत्वों को जोड़ें और इसे एक तत्व बनाएं। } चरण 4: चरण 1 पर जाएं

उदाहरण

#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