इस लेख में, हम C++ का उपयोग करके K से कम योग वाले उप-सरणियों की संख्या का पता लगाएंगे। इस समस्या में, हमारे पास एक सरणी arr[] और एक पूर्णांक K है। तो अब हमें ऐसे उप-सरणियाँ ढूँढ़नी होंगी जिनका योग K से कम है। यहाँ उदाहरण है -
Input : arr[] = {1, 11, 2, 3, 15}
K = 10
Output : 4
{1}, {2}, {3} and {2, 3} समाधान खोजने के लिए दृष्टिकोण
अब हम दी गई समस्या को हल करने के लिए दो अलग-अलग विधियों का उपयोग करेंगे -
क्रूर फ़ोर्स
इस दृष्टिकोण में, हम सभी उप-सरणियों के माध्यम से पुनरावृति करेंगे और उनके योग की गणना करेंगे और k से तुलना करेंगे यदि योग हमारे उत्तर को बढ़ाने के लिए k से कम है।
उदाहरण
#include <bits/stdc++.h>
using namespace std;
int main(){
int arr[] = {1, 11, 2, 3, 15}; // given array
int k = 10; // given k
int size = sizeof(arr) / sizeof(int); // size of our array.
int ans = 0; // counter variable.
for(int i = 0; i < size; i++){ // outer loop.
int sum = 0;
for(int j = i; j < size; j++){ // inner loop.
sum = sum + arr[j];
if(sum < k) // comparing with k.
ans++; // incrementing our ans if sum is less than k.
}
}
cout << ans << "\n";
return 0;
} आउटपुट
4
हालांकि, यह दृष्टिकोण बहुत अच्छा नहीं है क्योंकि इसमें समय की जटिलता बहुत अधिक है O(N*N) , जहां n हमारे सरणी का आकार है।
हम स्लाइडिंग विंडो विधि का उपयोग करके एक वैकल्पिक समाधान देखेंगे (जो हमें कार्यक्रम की समय जटिलता को कम करने में मदद करेगा)।
कुशल दृष्टिकोण
ब्रूट फ़ोर्स के विपरीत , हम सभी उपसरणियों से नहीं गुजरेंगे। इसके बजाय, हम तभी ट्रैवर्स करेंगे जब एक सबएरे का योग k से अधिक हो जाता है और हमारी बाईं सीमा को हमारी दाहिनी सीमा तक ले जाता है और तब तक दोहराता रहता है जब तक कि पूरे एरे का पता नहीं चल जाता।
उदाहरण
#include <bits/stdc++.h>
using namespace std;
int main(){
int arr[] = {1, 11, 2, 3, 15}; // given array
int k = 10; // given k
int size = sizeof(arr) / sizeof(int); // size of our array.
int ans = 0; // counter variable.
int start = 0; // left border.
int end = 0; // right border.
int sum = 0;
while(end < size && start < size){ // till the whole array is traversed.
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++ प्रोग्राम और संपूर्ण दृष्टिकोण (सामान्य और कुशल) भी सीखा जिसके द्वारा हमने इस समस्या को हल किया। हम उसी प्रोग्राम को अन्य भाषाओं जैसे सी, जावा, पायथन और अन्य भाषाओं में लिख सकते हैं। आशा है कि आपको यह लेख मददगार लगा होगा।