मान लीजिए हमारे पास N पूर्णांकों की एक सरणी दी गई है जिसका कार्य शून्य योग वाले अधिकतम लंबाई के सबएरे की लंबाई ढूंढना है। यदि ऐसा कोई सबएरे नहीं है जिसकी लंबाई अधिकतम हो या योग 0 के बराबर हो तो '0' लौटाएं। उदाहरण के लिए,
इनपुट-1 -
N = 8 A[] = {15, -5, -1, 5, 1, 4}
आउटपुट -
4
व्याख्या - शून्य-योग वाला सबसे बड़ा सबएरे {-5, -1, 5, 1} है जिसकी लंबाई 4 है।
इनपुट-2 -
N = 5 A[] = {3, 2, 4, 8, -1}
आउटपुट -
0
व्याख्या - चूंकि कोई सबएरे मौजूद नहीं है जिसका योग शून्य के बराबर हो, आउटपुट '0' है।
इस प्रॉब्लम को हल करने का दृष्टिकोण
इस विशेष प्रॉब्लम को हल करने के कई दृष्टिकोण हैं। रैखिक समय O(n) में हल करने के लिए सबसे उपयुक्त एल्गोरिदम हैश टेबल का उपयोग करना है।
विचार यह है कि एक हैश टेबल बनाई जाए जो उन सभी सबएरे के योग को संग्रहीत करे जिनका योग कुंजी के रूप में संग्रहीत है और इंडेक्स वैल्यू के रूप में।
हम पहले पूरी सरणी को पार करेंगे और वर्तमान योग को स्टोर करेंगे। हम जांचेंगे कि क्या वर्तमान योग हैश टेबल में उपलब्ध है या नहीं। यदि यह हैशटेबल में मौजूद है, तो सबएरे की अधिकतम लंबाई को अपडेट करें।
N आकार की सरणी का इनपुट लें।
एक फंक्शन lenMax(int *arr, int size) एक सरणी और उसके आकार को इनपुट के रूप में लेता है जो शून्य योग वाले सबएरे की अधिकतम लंबाई लौटाता है।
पूर्णांक का एक अनऑर्डर्ड मैप जिसमें कुंजी योग के रूप में और वैल्यू इंडेक्स के रूप में हो, जांचें कि क्या कोई योग दोहरा रहा है या नहीं।
सरणी तत्व पर पुनरावृति करें और सरणी का वर्तमान योग ढूंढें यदि योग हैशटेबल में मौजूद है, तो सबएरे की अधिकतम लंबाई ढूंढें। यदि नहीं, तो नए योग और उसके इंडेक्स के साथ हैशटेबल में डालें।
आउटपुट के रूप में अधिकतम लंबाई लौटाएं।
उदाहरण
#include <bits/stdc++.h>
using namespace std;
int lenMax(int *arr, int size) {
unordered_map<int, int> mp;
int sum = 0;
int maxlen = 0;
for (int i = 0; i < size; i++) {
sum += arr[i];
if (arr[i] == 0 && maxlen == 0) {
maxlen = 1;
}
if (sum == 0) {
maxlen = i + 1;
}
if (mp.find(sum) != mp.end()) {
maxlen = max(maxlen, i - mp[sum]);
} else {
mp[sum] = i;
}
}
return maxlen;
}
int main() {
int N = 8;
int A[N] = {15, -2, 2, -8, 1, 7, 10, 23};
cout << lenMax(A, N) << endl;
return 0;
}
आउटपुट
यदि हम उपरोक्त कोड चलाएंगे, तो यह आउटपुट के रूप में प्रिंट करेगा,
5
शून्य योग वाला सबसे बड़ा सबएरे {-2, 2, -8, 1, 7} है। इस प्रकार, सबसे बड़े सबएरे की लंबाई '5' है।
