इस समस्या में, हमें एक सरणी arr [] दिया जाता है जिसमें N धनात्मक पूर्णांकों को क्रमबद्ध क्रम में संग्रहीत किया जाता है। हमारा काम है दी गई राशि के साथ एक उप-सरणी ढूंढना ।
समस्या को समझने के लिए एक उदाहरण लेते हैं,
Input : arr[] = {2, 5, 1, 4, 6, 9, 5} sum = 11
Output : subarray = {1, 4, 6} स्पष्टीकरण -
Subarray sum = 1 + 4 + 6 = 11
समाधान दृष्टिकोण
समस्या का एक आसान समाधान नेस्टेड लूप का उपयोग कर रहा है। हम सरणी के माध्यम से लूप करेंगे और एक आंतरिक लूप का उपयोग करके, हम सबएरे पाएंगे। प्रत्येक उप-सरणी के लिए हम सभी तत्वों का योग ज्ञात करेंगे और इसकी तुलना दिए गए योग मान से करेंगे। यदि यह बराबर है, तो सबअरे प्रिंट करें। यदि सरणी के सभी तत्वों को पार किया जाता है, तो ऐसा कोई सरणी नहीं मिला प्रिंट करें।
एल्गोरिदम
-
चरण 1 - सरणी के माध्यम से लूप करें, i -> 0 से (n-1)।
-
चरण 1.1 - प्रत्येक तत्व के लिए, सभी संभावित उप-सरणी के लिए प्रत्येक उप-सरणी का योग ज्ञात करें।
-
चरण 1.2 - यदि वर्तमान योग सरणी तत्वों का योग दिए गए उप-सरणी के बराबर है, तो उप-सरणी को प्रिंट करें।
-
-
चरण 2 -यदि सरणी के सभी तत्वों का पता लगाया जाता है और कोई उप-सरणी नहीं मिलती है। प्रिंट करें "दी गई राशि के साथ कोई उप-सरणी नहीं मिली!"।
उदाहरण
हमारे समाधान की कार्यप्रणाली को दर्शाने के लिए कार्यक्रम
#include <bits/stdc++.h>
using namespace std;
void printSubArray(int arr[], int i, int j){
cout<<"{";
for(; i < j; i++)
cout<<arr[i]<<" ";
cout<<"}";
}
int findSubArrayWithSum(int arr[], int n, int sum) {
int currSum;
for (int i = 0; i < n; i++) {
currSum = arr[i];
for (int j = i + 1; j <= n; j++) {
if (currSum == sum) {
cout<<"Subarray with given sum : ";
printSumArray(arr, i, j); return 1;
}
if (currSum > sum || j == n)
break;
currSum = currSum + arr[j];
}
}
cout<<"No subarray found";
return 0;
}
int main() {
int arr[] = { 2, 5, 1, 4, 6, 9, 3};
int n = sizeof(arr) / sizeof(arr[0]);
int sum = 11;
findSubArrayWithSum(arr, n, sum);
return 0;
} आउटपुट
Subarray with given sum : { 1 4 6 } समस्या को हल करने का एक बेहतर तरीका स्लाइडिंग विंडो के समान एक विधि का उपयोग करना है, लेकिन यहां हमारे पास एक चर विंडो होगी। हम सरणी के पहले तत्व से शुरू करेंगे, विंडो में तत्वों को तब तक जोड़ेंगे जब तक योग दिए गए योग से अधिक न हो जाए। यदि यह तत्वों को हटाने से बड़ा हो जाता है जब तक कि यह फिर से योग से कम न हो जाए। इस प्रक्रिया को तब तक करें जब तक कि पूरा ऐरे ट्रेस न हो जाए।
यदि किसी बिंदु पर, विंडो योग दिए गए योग के बराबर हो जाता है, तो सबअरे प्रिंट करें। और यदि दिए गए योग के बराबर कोई विंडो नहीं मिलेगी और कोई तत्व ट्रेस नहीं किया जाना है, तो प्रिंट करें "कोई सबरे नहीं मिला!" ।
एल्गोरिदम
आरंभ करें -विंडोसम =0, सिन्डेक्स =0, एंडइंडेक्स =0
-
चरण 1 - एंडइंडेक्स का उपयोग करके सरणी को पार करें।
-
चरण 1.1 -विंडोसम को तब तक अपडेट करें जब तक कि विंडोसम योग से अधिक न हो जाए यानी अगर (विंडोसम <योग) -> विंडोसम =विंडोसम + एआर [एंडइंडेक्स]।
-
चरण 1.2 - यदि विंडोसम योग से अधिक है, तो तत्वों को हटाकर विंडो का आकार कम करें, अर्थात जबकि (विंडोसम <योग) -> विंडोसम =विंडोसम - एआर [एंडइंडेक्स]।
-
चरण 1.3 - अगर विंडोसम ==योग, प्रिंट सबरे।
-
-
चरण 2 - अगर ऐरे को ट्रेस किया जाता है, तो प्रिंट करें -> 'संभव नहीं'।
उदाहरण
हमारे समाधान की कार्यप्रणाली को दर्शाने के लिए कार्यक्रम
#include <bits/stdc++.h>
using namespace std;
void printSubArray(int arr[], int i, int j){
cout<<"{ ";
for(; i < j; i++)
cout<<arr[i]<<" ";
cout<<"}";
}
int findSubArrayWithSum(int arr[], int n, int sum) {
int windowSum = arr[0], startIndex = 0, endIndex;
for (endIndex = 1; endIndex <= n; endIndex++) {
while (windowSum > sum && startIndex < endIndex - 1) {
windowSum -= arr[startIndex];
startIndex++;
}
if (windowSum == sum) {
cout << "Subarray with given sum : ";
printSumArray(arr, startIndex ,endIndex);
return 1;
}
if (endIndex < n)
windowSum += arr[endIndex];
}
cout << "No subarray found";
return 0;
}
int main() {
int arr[] = { 2, 5, 1, 4, 6, 9, 3};
int n = sizeof(arr) / sizeof(arr[0]);
int sum = 11;
findSubArrayWithSum(arr, n, sum);
return 0;
} आउटपुट
Subarray with given sum : { 1 4 6 }