इस लेख में, हम C++ प्रोग्राम का उपयोग करके दी गई रेंज में योग वाले सबअर्रे की संख्या को हल करेंगे। हमारे पास धनात्मक पूर्णांकों की एक सरणी arr[] है, और एक रेंज {L, R} है और हमें दी गई रेंज L से R में योग वाले सबअर्रे की कुल संख्या की गणना करनी है। तो यहाँ समस्या के लिए एक सरल उदाहरण है:
Input : arr[] = {1, 4, 6}, L = 3, R = 8 Output : 3 सबअर्रे हैं {1, 4}, {4}, {6}। Input : arr[] = {2, 3, 5, 8}, L = 4, R = 13 Output : 6 सबअर्रे हैं {2, 3}, {2, 3, 5}, {3, 5}, {5}, {5, 8}, {8}।समाधान खोजने के दृष्टिकोण
हम C++ का उपयोग करके इस समस्या को हल करने के लिए दो विधियों की व्याख्या करेंगे:
ब्रूट फोर्स दृष्टिकोण
सबसे बुनियादी ब्रूट फोर्स दृष्टिकोण हर सबअर्रे के योग की गणना करना है और फिर पता लगाना है कि वह योग दी गई रेंज में मौजूद है या नहीं। (लेकिन यह दृष्टिकोण हमें बहुत समय लगेगा क्योंकि इसकी समय जटिलता O(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 n; // सरणी का आकार int L, R; cin >> n; int arr[n]; for(int i = 0; i < n; i++) cin >> arr[i]; cin >> L >> R; int answer; answer = subCount(arr, n, R) - subCount(arr, n, (L - 1)); // अंतिम उत्तर cout << answer << "\n"; return 0; }आउटपुट
1
उपरोक्त कोड की व्याख्या
इस दृष्टिकोण में, हम दी गई रेंज की ऊपरी सीमा से कम योग वाले सबअर्रे की संख्या गिन रहे हैं, और फिर हम अपने subcount फ़ंक्शन का उपयोग करके दी गई रेंज की निचली सीमा से कम योग वाले सबअर्रे की संख्या घटा रहे हैं।
Subcount फ़ंक्शन
यह फ़ंक्शन x से कम गिनती वाले सबअर्रे की गिनती खोजने के लिए स्लाइडिंग विंडो तकनीक का उपयोग करता है।
सबसे पहले, हम 'end और start' दोनों को 0 मान के साथ शुरू करते हैं। जैसे ही हम सरणी को पार करते हैं, हम start से end तक के तत्वों का योग बनाए रखते हैं। उसके बाद, यदि हमारा start हमारे end के बराबर है और योग x से अधिक या बराबर है, तो हम अपने start को मूव करना शुरू करते हैं और जैसे ही हम योग से तत्वों को हटाते हैं, अपने योग को घटाते रहते हैं।
जब तक हमारा योग x से कम नहीं हो जाता या हमारा start end से अधिक नहीं हो जाता। अब हम सबअर्रे गिनती से गिनती बढ़ाते हैं और फिर दाएं बॉर्डर को 1 से बढ़ाते हैं। अब, हमारे बाहरी लूप के समाप्त होने के बाद, हम अपने सबअर्रे की कुल गिनती लौटाते हैं।
निष्कर्ष
इस लेख में, हम स्लाइडिंग विंडो तकनीक का उपयोग करके O(n) समय जटिलता में दी गई रेंज में योग वाले सबअर्रे की संख्या ज्ञात करने की समस्या को हल करते हैं। हमने इस समस्या के लिए C++ प्रोग्राम और पूरा दृष्टिकोण (सामान्य और कुशल) भी सीखा जिससे हम इस समस्या को आसानी से हल कर सकते हैं। हम इसी प्रोग्राम को C, Java, Python आदि अन्य भाषाओं में लिख सकते हैं।
