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

C++ का उपयोग करके K से कम योग वाले सबअर्रे की संख्या ज्ञात करें


इस लेख में, हम C++ का उपयोग करके K से कम योग वाले सबअर्रे की संख्या ज्ञात करेंगे। इस समस्या में, हमारे पास एक सरणी arr[] और एक पूर्णांक K है। अब हमें उन सबअर्रे को ढूंढना है जिनका योग K से कम है। यहाँ एक उदाहरण है:

Input : arr[] = {1, 11, 2, 3, 15} K = 10 Output : 4 {1}, {2}, {3} और {2, 3}

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

हम दी गई समस्या को हल करने के लिए दो अलग-अलग विधियों का उपयोग करेंगे:

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

इस दृष्टिकोण में, हम सभी सबअर्रे के माध्यम से पुनरावृति करेंगे और उनके योग की गणना करेंगे, फिर K के साथ तुलना करेंगे। यदि योग K से कम है तो हम अपने उत्तर को बढ़ाएंगे।

उदाहरण

#include <bits/stdc++.h> using namespace std; int main(){     int arr[] = {1, 11, 2, 3, 15}; // दी गई सरणी     int k = 10; // दिया गया k     int size = sizeof(arr) / sizeof(int); // हमारी सरणी का आकार     int ans = 0; // काउंटर चर     for(int i = 0; i < size; i++){ // बाहरी लूप         int sum = 0;         for(int j = i; j < size; j++){ // आंतरिक लूप             sum = sum + arr[j];             if(sum < k) // k के साथ तुलना                 ans++; // यदि योग k से कम है तो ans बढ़ाएं         }     }     cout << ans << "\n";     return 0; }

आउटपुट

4

हालांकि, यह दृष्टिकोण बहुत अच्छा नहीं है क्योंकि इसकी समय जटिलता बहुत अधिक है O(N²), जहां n हमारी सरणी का आकार है।

हम स्लाइडिंग विंडो विधि का उपयोग करके एक वैकल्पिक समाधान देखेंगे (जो हमारे प्रोग्राम की समय जटिलता को कम करने में मदद करेगा)।

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

ब्रूट फोर्स के विपरीत, हम सभी सबअर्रे के माध्यम से नहीं जाएंगे। इसके बजाय, हम केवल तभी पार करेंगे जब किसी सबअर्रे का योग k से अधिक हो जाए और अपने बाएं बॉर्डर को तब तक मूव करेंगे जब तक यह हमारे दाएं बॉर्डर तक न पहुंच जाए, और पूरी सरणी पार होने तक इसे दोहराएंगे।

उदाहरण

#include <bits/stdc++.h> using namespace std; int main(){     int arr[] = {1, 11, 2, 3, 15}; // दी गई सरणी     int k = 10; // दिया गया k     int size = sizeof(arr) / sizeof(int); // हमारी सरणी का आकार     int ans = 0; // काउंटर चर     int start = 0; // बायां बॉर्डर     int end = 0; // दायां बॉर्डर     int sum = 0;     while(end < size && start < size){ // जब तक पूरी सरणी पार न हो जाए         while(sum >= k && start < end){             sum = sum - arr[start];             start++;         }         if(end >= start)             ans = ans + end - start;         sum += arr[end];         end++;     }     cout << ans << "\n";     return 0; }

आउटपुट

4

इस दृष्टिकोण में हम स्लाइडिंग विंडो तकनीक का उपयोग करते हैं ताकि हमारा प्रोग्राम बड़े प्रतिबंधों के लिए तेज़ और समय-कुशल हो सके।

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

इस दृष्टिकोण में, हम सामान्य रूप से तब तक पार करते हैं जब तक हमारा योग k से कम है और उसके अनुसार अपना उत्तर बढ़ाते हैं। अब कोड में महत्वपूर्ण परिवर्तन तब होता है जब योग k से अधिक या बराबर हो जाता है। इस स्थिति में, हम अपने बाएं बॉर्डर को अपने दाएं बॉर्डर से छोटा करना शुरू करते हैं या तब तक जब तक योग k से अधिक या बराबर है। जैसे-जैसे हम आगे बढ़ते हैं, यह उन अन्य सबअर्रे के माध्यम से पार करता है जो बनाए जा सकते हैं। इन नए सबअर्रे जिनका योग k से कम है, उन्हें हमारे उत्तर में जोड़ा जाता है, इसलिए हमारा उत्तर बढ़ता है।

यह दृष्टिकोण पहले लागू किए गए ब्रूट फोर्स की तुलना में बहुत कुशल है क्योंकि इसकी समय जटिलता O(N) है, जहां N हमारी सरणी का आकार है।

निष्कर्ष

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


  1. C++ का उपयोग करके पेंटागोनल पिरामिडल संख्या ज्ञात करना C++ का उपयोग करके पेंटागोनल पिरामिडल संख्या ज्ञात करना

    एक पेंटागोनल पिरामिडल संख्या पेंटागोनल बेस पिरामिड में वस्तुओं की संख्या के बराबर होती है। नीचे कुछ पेंटागोनल संख्याएं देखें। N तक पेंटागोनल संख्याओं का योग Nवीं पेंटागोनल पिरामिडल संख्या के बराबर होता है। इस लेख में, हम Nवीं पेंटागोनल पिरामिडल संख्या खोजने पर चर्चा करेंगे, उदाहरण के लिए: इनपुट:

  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 स्टेशनों पर रुकने के लिए व्यवस्थित किया जा सकता है जैसे कि कोई दो स्टेशन एक-दूसरे के बगल में न हों। तो इस लेख में, हम स्टॉपिंग स्टेशनों की संख्या ज्ञात करने के लिए हर संभव दृष्टिकोण की व्य