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

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

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

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

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

एल्गोरिदम

इनपुट - ऐरे और के

Step 1 : check if all elements are greater than or equal to K
Step 2: if(yes){
   Print number of iterations.
}
exit(0)
Step 3: else {
   Add smallest two elements of the array and make it one element.
}
Step 4: goto step 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