इस लेख में, हम C++ प्रोग्राम का उपयोग करके दी गई श्रेणी में योग वाले उप-सरणियों की संख्या को हल करेंगे। हमारे पास धनात्मक पूर्णांकों की एक सरणी arr[] है, और एक श्रेणी {L, R} है और हमें दिए गए श्रेणी रूप L से R में योग वाले उप-सरणियों की कुल संख्या की गणना करनी है। तो यहाँ समस्या का सरल उदाहरण है -
Input : arr[] = {1, 4, 6}, L = 3, R = 8
Output : 3
The subarrays are {1, 4}, {4}, {6}.
Input : arr[] = {2, 3, 5, 8}, L = 4, R = 13
Output : 6
The subarrays are {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){ // we will be moving right border in this loop
sum = sum + arr[end];
while(start <= end && sum >= x){ // this loop will move our left border
sum = sum - arr[start]; // we will decrement sum while moving left border.
// For excluding the previous elements.
start++; // and move the left border.
}
count = count + ((end - start) + 1); // counting the subarrays.
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)); // Final Answer.
cout << answer << "\n";
return 0;
} आउटपुट
3
उपरोक्त कोड की व्याख्या
इस दृष्टिकोण में, हम दी गई सीमा की ऊपरी सीमा से कम योग के साथ उप-सरणियों की संख्या की गणना कर रहे हैं, और फिर हम उन उप-सरणियों की संख्या घटा रहे हैं, जिनका योग हमारे उप-गणना फ़ंक्शन का उपयोग करके हमारी दी गई सीमा की निचली सीमा से कम है।
सबकाउंट फंक्शन
यह फ़ंक्शन स्लाइडिंग विंडो तकनीक का उपयोग उन सबएरे की गिनती खोजने के लिए करता है जिनकी गिनती x से कम है।
सबसे पहले, हम 'एंड एंड स्टार्ट' दोनों से शुरू करते हैं, जिसका मान 0 है। जैसा कि हम सरणी को पार करते हैं, हम शुरू से अंत तक तत्वों का योग बनाए रखते हैं। उसके बाद, यदि हमारी शुरुआत हमारे अंत के बराबर है और योग x के बराबर या अधिक है, तो हम अपनी शुरुआत को आगे बढ़ाना शुरू कर देते हैं और अपना योग घटाते रहते हैं क्योंकि हम योग से तत्वों को हटा रहे हैं।
जब तक हमारा योग x से कम न हो जाए या हमारा प्रारंभ अंत से बड़ा न हो जाए। अब हम सबअरे काउंट द्वारा काउंट बढ़ाते हैं और फिर 1 के साथ दायें बॉर्डर को बढ़ाते हैं। अब, हमारे बाहरी लूप के समाप्त होने के बाद, हम अपने सबएरे की कुल काउंट लौटाते हैं।
निष्कर्ष
इस लेख में, हम स्लाइडिंग विंडो तकनीक का उपयोग करके ओ (एन) समय जटिलता में दी गई सीमा में योग वाले उप-सरणियों की संख्या को खोजने के लिए एक समस्या का समाधान करते हैं। हमने इस समस्या के लिए C++ प्रोग्राम और संपूर्ण दृष्टिकोण (सामान्य और कुशल) से भी सीखा जिससे हम इस समस्या को आसानी से हल कर सकते हैं। हम उसी प्रोग्राम को अन्य भाषाओं जैसे C, java, python, आदि में भी लिख सकते हैं।