Computer >> कंप्यूटर ट्यूटोरियल >  >> प्रोग्रामिंग >> C++

C++ में दी गई रेंज में योग वाले सबएरे की संख्या


इस लेख में, हम C++ प्रोग्राम का उपयोग करके दी गई रेंज में योग वाले सबएरे की संख्या को हल करेंगे। हमारे पास धनात्मक पूर्णांकों की एक सरणी arr[] है, और एक रेंज {L, R} है और हमें L से R तक दी गई रेंज में योग वाले सबएरे की कुल संख्या की गणना करनी है। तो यहां समस्या के लिए एक सरल उदाहरण है -

इनपुट: arr[] = {1, 4, 6}, L = 3, R = 8 आउटपुट: 3 सबएरे हैं {1, 4}, {4}, {6}। इनपुट: arr[] = {2, 3, 5, 8}, L = 4, R = 13 आउटपुट: 6 सबएरे हैं {2, 3}, {2, 3, 5}, {3, 5}, {5}, {5, 8}, {8}।

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

हम इस समस्या को हल करने के लिए C++ प्रोग्राम का उपयोग करके दो विधियों को समझाएंगे -

ब्रूट फोर्स दृष्टिकोण

सबसे बुनियादी ब्रूट फोर्स दृष्टिकोण हर सबएरे का योग निकालना है और फिर पता लगाना है कि वह योग दी गई रेंज में मौजूद है या नहीं। (लेकिन यह दृष्टिकोण हमें बहुत समय खर्च करेगा क्योंकि इसकी समय जटिलता O(n*n) है जहां n सरणी का आकार है)।

कुशल दृष्टिकोण

समय बचाने के लिए, हम एक और विधि का उपयोग करते हैं जिसे कुशल दृष्टिकोण के रूप में जाना जाता है। अब कुशल दृष्टिकोण स्लाइडिंग विंडो तकनीक का उपयोग कर रहा है, इस तकनीक का उपयोग करके हम अपना परिणाम बहुत तेजी से या कुशलता से O(n) में निकालेंगे।

उदाहरण

 #include <bits/stdc++.h> using namespace std; int subCount(int *arr, int n, int x){     int start = 0, end = 0, sum = 0, count = 0;     while (end < n){ // हम इस लूप में राइट बॉर्डर को आगे बढ़ाएंगे         sum = sum + arr[end];         while(start <= end && sum >= x){ // यह लूप हमारे लेफ्ट बॉर्डर को आगे बढ़ाएगा             sum = sum - arr[start]; // लेफ्ट बॉर्डर को आगे बढ़ाते हुए योग घटाएंगे।                                    // पिछले तत्वों को बाहर करने के लिए।             start++;                // और लेफ्ट बॉर्डर को आगे बढ़ाएं।         }         count = count + ((end - start) + 1); // सबएरे गिनना।         end++;     }     return count; } int main(){     int arr[] = { 1, 4, 6 };     int n = sizeof(arr) / sizeof(arr[0]);     int L = 3;     int R = 8;     int answer;     answer = subCount(arr, n, R) - subCount(arr, n, (L - 1)); // अंतिम उत्तर।     cout << answer << "\n";     return 0; }

आउटपुट

3

उपरोक्त कोड की व्याख्या

इस दृष्टिकोण में, हम दी गई रेंज की ऊपरी सीमा से कम योग वाले सबएरे की संख्या गिन रहे हैं, और फिर हम अपने subcount फंक्शन का उपयोग करके अपनी दी गई रेंज की निचली सीमा से कम योग वाले सबएरे की संख्या घटा रहे हैं।

Subcount फंक्शन

यह फंक्शन x से कम योग वाले सबएरे की गिनती खोजने के लिए स्लाइडिंग विंडो तकनीक का उपयोग करता है।

सबसे पहले, हम 'end और start' दोनों को 0 से उनके मान के साथ शुरू करते हैं। जैसे ही हम सरणी को पार करते हैं, हम start से end तक के तत्वों का योग बनाए रखते हैं। उसके बाद, यदि हमारा start हमारे end के बराबर है और योग x से बड़ा या बराबर है, तो हम अपना start आगे बढ़ाना शुरू करते हैं और अपने योग को घटाते रहते हैं क्योंकि हम योग से तत्वों को हटा रहे हैं।

जब तक हमारा योग x से कम नहीं हो जाता या हमारा start end से बड़ा नहीं हो जाता। अब हम काउंट को सबएरे काउंट से बढ़ाते हैं और फिर राइट बॉर्डर को 1 से बढ़ाते हैं। अब, हमारे बाहरी लूप के समाप्त होने के बाद, हम अपने सबएरे की कुल गिनती लौटाते हैं।

निष्कर्ष

इस लेख में, हम स्लाइडिंग विंडो तकनीक का उपयोग करके O(n) समय जटिलता में दी गई रेंज में योग वाले सबएरे की संख्या निकालने की समस्या को हल करते हैं। हमने इस समस्या के लिए C++ प्रोग्राम और पूरा दृष्टिकोण (सामान्य और कुशल) भी सीखा जिससे हम इस समस्या को आसानी से हल कर सकते हैं। हम यही प्रोग्राम C, Java, Python आदि अन्य भाषाओं में भी लिख सकते हैं।

  1. C++ में स्ट्रिंग के सबस्ट्रिंग्स की संख्या निकालना C++ में स्ट्रिंग के सबस्ट्रिंग्स की संख्या निकालना

    इस लेख में, आप एक दी गई स्ट्रिंग में बनने वाले सबस्ट्रिंग्स (गैर-खाली) की संख्या निकालने के दृष्टिकोण के बारे में जानेंगे।इनपुट: string = moon आउटपुट: 10 व्याख्या: सबस्ट्रिंग्स हैं m, o, o, n, mo, oo, on, moo, oon और moon। इनपुट: string = yellow आउटपुट: 21समाधान खोजने का दृष्टिकोणमान लें स्ट्रिंग की

  1. C++ का उपयोग करके स्टॉपिंग स्टेशनों की संख्या ज्ञात करें C++ का उपयोग करके स्टॉपिंग स्टेशनों की संख्या ज्ञात करें

    बिंदु X और Y के बीच n संख्या में इंटरमीडिएट ट्रेन स्टेशन हैं। उन विभिन्न तरीकों की गणना करें जिनसे ट्रेनों को s स्टेशनों पर रुकने के लिए व्यवस्थित किया जा सकता है जैसे कि कोई दो स्टेशन एक-दूसरे के बगल में न हों। तो इस लेख में, हम स्टॉपिंग स्टेशनों की संख्या ज्ञात करने के लिए हर संभव दृष्टिकोण की व्य

  1. C++ का उपयोग करके दिए गए बिंदुओं से संभावित चतुर्भुजों की संख्या ज्ञात करें C++ का उपयोग करके दिए गए बिंदुओं से संभावित चतुर्भुजों की संख्या ज्ञात करें

    यूक्लिडियन प्लेन ज्यामिति में एक चतुर्भुज चार शीर्षों और चार किनारों के साथ एक बहुभुज बनाता है। नाम 4-gon आदि। चतुर्भुजों के अन्य नामों में शामिल हैं और कभी-कभी उन्हें वर्ग, डिस्प्ले स्टाइल आदि के रूप में भी जाना जाता है।इस लेख में, हम दिए गए बिंदुओं से संभावित चतुर्भुजों की संख्या ज्ञात करने के दृष