इस लेख में, हम 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 और अन्य भाषाओं में भी लिख सकते हैं। आशा है आपको यह लेख उपयोगी लगा होगा।