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

समस्या विवरण

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

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

उदाहरण: array[] = {5, 2, 9, 4, 1}

prefixSumArray[] = {5, 7, 16, 20, 21}

उदाहरण

इनपुट: arr[] = {5, 2, 9, 4, 1}, X = 19
आउटपुट: 3 (0-आधारित इंडेक्स)

व्याख्या: प्रीफिक्स योग [5, 7, 16, 20, 21]। 19 से ≥ पहला मान 20 है जो इंडेक्स 3 पर है।

हल का दृष्टिकोण

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

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

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

• या तो लक्ष्य स्थिति 'position + 2^i' और 'position + 2^(i+1)' के बीच है जहां i-वें लिफ्ट ने मान बढ़ाया
• या, लक्ष्य स्थिति 'position' और 'position + 2^i' के बीच है

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

C++ कार्यान्वयन

#include <iostream> 
#include <cmath> 
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 pos = 0;
    int LOGN = log2(n);
    
    if (x <= prefSum[0])
        return 0;
    
    for (int i = LOGN; i >= 0; i--) {
        int nextPos = pos + (1 << i);
        if (nextPos < n && prefSum[nextPos] < x) {
            pos = nextPos;
        }
    }
    return pos + 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 << "दिए गए नंबर से बड़ा सरणी का पहला तत्व इंडेक्स है ";
    cout << findPreSumIndexBL(prefSum, n, X);
    return 0;
}

आउटपुट

दिए गए नंबर से बड़ा सरणी का पहला तत्व इंडेक्स है 3

जटिलता विश्लेषण

• प्रीफिक्स योग निर्माण: O(N)
• बाइनरी लिफ्टिंग क्वेरी: O(log N)
• कुल: O(N + log N) प्रति क्वेरी (प्रीकंप्यूटेशन के बाद)
• स्पेस: O(N)

बाइनरी लिफ्टिंग अंतर्ज्ञान

बाइनरी लिफ्टिंग बाइनरी प्रतिनिधित्व का उपयोग करके उत्तर की ओर "कूदती" है। सबसे बड़ी 2 की घात से शुरू करके, यह जांचता है कि क्या उस आकार की छलांग उत्तर से पहले रखती है। यदि हां, तो छलांग लें। यह बाइनरी खोज के समान है लेकिन स्पष्ट मध्य गणना के बिना।