C++ में बाइनरी लिफ्टिंग का उपयोग करते हुए N संख्याओं के उपसर्ग योग में X से बड़ा या उसके बराबर पहला तत्व

इस समस्या में, हमें एक सरणी arr [] दिया जाता है जिसमें N संख्याएँ और एक पूर्णांक मान x होता है। हमारा काम है बाइनरी लिफ्टिंग का उपयोग करके एन नंबरों के उपसर्ग योग में एक्स से बड़ा या उसके बराबर पहला तत्व खोजने के लिए एक प्रोग्राम बनाना ।

उपसर्ग योग एक सरणी के तत्वों का एक सरणी है जिसका प्रत्येक तत्व प्रारंभिक सरणी में उस अनुक्रमणिका तक सभी तत्वों का योग है।

उदाहरण - सरणी [] ={5, 2, 9, 4, 1}

उपसर्गसुमअरे [] ={5, 7, 16, 20, 21}

समस्या को समझने के लिए एक उदाहरण लेते हैं,

Input: arr[] = {5, 2, 9, 4, 1}, X = 19
Output: 3

समाधान दृष्टिकोण

यहां, हम बाइनरी लिफ्टिंग . की अवधारणा का उपयोग करके समस्या का समाधान करेंगे . बाइनरी लिफ्टिंग दी गई संख्या के मूल्य को 2 की शक्तियों (बिट्स को फ़्लिप करके) 0 से एन तक बढ़ा रही है।

हम बाइनरी ट्री उठाने के समान एक अवधारणा पर विचार करेंगे जहां हम 'पी' इंडेक्स का प्रारंभिक मूल्य पाएंगे। यह सुनिश्चित करने के लिए बिट्स को फ़्लिप करके बढ़ाया जाता है कि मान X से अधिक नहीं है। अब, हम इस स्थिति 'P' के साथ लिफ्ट पर भी विचार करेंगे।

इसके लिए, हम संख्या के बिट्स को इस तरह से फ़्लिप करना शुरू करेंगे कि i-th बिट फ़्लिप योग को X से बड़ा न बना दे। अब, हमारे पास 'P' के मान के आधार पर दो केस हैं -

या तो लक्ष्य स्थिति 'स्थिति + 2^i . के बीच स्थित है ' और 'स्थिति + 2^(i+1) ' जहां ith लिफ्ट ने मूल्य में वृद्धि की। या, लक्ष्य स्थिति 'स्थिति . के बीच स्थित है ' और 'स्थिति + 2^i '।

इसका उपयोग करके हम सूचकांक की स्थिति पर विचार करेंगे।

उदाहरण

हमारे समाधान की कार्यप्रणाली को दर्शाने के लिए कार्यक्रम

#include <iostream>
#include <math.h>
using namespace std;
void generatePrefixSum(int arr[], int prefSum[], int n){
   prefSum[0] = arr[0];
   for (int i = 1; i < n; i++)
      prefSum[i] = prefSum[i - 1] + arr[i];
}
int findPreSumIndexBL(int prefSum[], int n, int x){
   int P = 0;
   int LOGN = log2(n);
   if (x <= prefSum[0])
      return 0;
   for (int i = LOGN; i >= 0; i--) {
      if (P + (1 << i) < n &&
         prefSum[P + (1 << i)] < x) {
         P += (1 << i);
      }
   }
   return P + 1;
}
int main(){
   int arr[] = { 5, 2, 9, 4, 1 };
   int X = 19;
   int n = sizeof(arr) / sizeof(arr[0]);
   int prefSum[n] = { 0 };
   generatePrefixSum(arr, prefSum, n);
   cout<<"The index of first elements of the array greater than the given number is ";
   cout<<findPreSumIndexBL(prefSum, n, X);
   return 0;
}

आउटपुट

The index of first elements of the array greater than the given number is 3