इस समस्या में, हमें पूर्णांक मानों वाली आकार n की एक सरणी arr[] दी गई है। हमारा कार्य जांचना है कि क्या शून्य योग वाला उपसरणी मौजूद है।
हमें जांचना है कि दी गई सरणी में कोई उप-सरणी है जिसमें सभी तत्वों का योग 0 के बराबर है।
समस्या को समझने के लिए एक उदाहरण लेते हैं,
इनपुट: arr[] = {3, 1, -2, 1, 4, 5}
आउटपुट: Yes
व्याख्या:
उपसरणी {1, -2, 1} का सभी मानों का योग 0 के बराबर है।
समाधान दृष्टिकोण:
समस्या का एक सरल समाधान सभी उपसरणी पर विचार करना और जांचना है कि सभी तत्वों का योग 0 के बराबर है या नहीं।
समस्या का एक और समाधान हैशिंग का उपयोग करना है। हमें सरणी पर लूप करना होगा और फिर वर्तमान सूचकांक तक योग ढूंढना होगा और इसे हैश टेबल में संग्रहीत करना होगा।
फिर हैश टेबल में जांचें, यदि योग मान पहले जैसा ही है तो योग = 0 वाला उपसरणी मिला।
यदि उपसरणी मिला तो True वापस करें
अन्यथा False वापस करें
हमारी समस्या के कार्यप्रणाली को दर्शाने वाला प्रोग्राम,
उदाहरण
#include <bits/stdc++.h>
using namespace std;
bool isSubArraySumZero(int arr[], int n) {
unordered_set<int> sumHash;
int currSum = 0;
for (int i = 0 ; i < n ; i++) {
currSum += arr[i];
if (currSum == 0 || sumHash.find(currSum) != sumHash.end())
return true;
sumHash.insert(currSum);
}
return false;
}
int main() {
int arr[] = { 3, 1, -2, 1, 4, 5 };
int n = sizeof(arr)/sizeof(arr[0]);
if (isSubArraySumZero(arr, n))
cout<<"SubArray with sum equal to 0 exists in the array";
else
cout<<"No subarray exists";
return 0;
}
आउटपुट
SubArray with sum equal to 0 exists in the array
