इस समस्या में, हमें एक सरणी arr[] दी गई है जिसमें n पूर्णांक मान हैं। हमारा कार्य दिए गए सरणी के सभी अद्वितीय सबएरे योग का योग ज्ञात करना है। सबएरे योग दिए गए सबएरे के तत्वों का योग है।
उदाहरण से समझते हैं:
इनपुट: arr[] = {1, 2, 4} आउटपुट: 23 व्याख्या:
दिए गए सरणी के सभी सबएरे हैं: (1), (2), (4), (1, 2), (2, 4), (1, 2, 4) सबएरे का योग = 1 + 2 + 4 + (1+2) + (2+4) + (1+2+4) = 23
समाधान दृष्टिकोण
समस्या का एक समाधान सबएरे योग को संग्रहीत करना और फिर उन्हें सॉर्ट करके अद्वितीय सबएरे ढूंढना है। फिर हम योग के लिए सभी अद्वितीय सबएरे पर विचार करेंगे।
एल्गोरिथम
चरण 1 - सभी सब-एरे का योग ज्ञात करें और इसे एक वेक्टर में संग्रहीत करें।
चरण 2 - वेक्टर को सॉर्ट करें।
चरण 3 - उन सभी वेक्टर पर विचार करें जो अद्वितीय हैं और बाकी का योग 0 चिह्नित करें।
चरण 4 - योग की गणना करें और प्रिंट करें।
उदाहरण
हमारे समाधान के कार्य को दर्शाने वाला प्रोग्राम:
#include <bits/stdc++.h> using namespace std; long int findSumOfSubArraySum(int arr[], int n){ int i, j; long int sumArrayTill[n + 1] = { 0 }; for (i = 0; i < n; i++) sumArrayTill[i + 1] = sumArrayTill[i] + arr[i]; vector<long int> subArraySum; for (i = 1; i <= n; i++) for (j = i; j <= n; j++) subArraySum.push_back(sumArrayTill[j] - sumArrayTill[i - 1]); sort(subArraySum.begin(), subArraySum.end()); for (i = 0; i < subArraySum.size() - 1; i++){ if (subArraySum[i] == subArraySum[i + 1]) { j = i + 1; while (subArraySum[j] == subArraySum[i] && j < subArraySum.size()){ subArraySum[j] = 0; j++; } subArraySum[i] = 0; } } long sum = 0; for (i = 0; i < subArraySum.size(); i++) sum += subArraySum[i]; return sum; } int main(){ int arr[] = { 1, 2, 4, 7, 9 }; int n = sizeof(arr) / sizeof(arr[0]); cout<<"The sum of all unique subarray sum is "<<findSumOfSubArraySum(arr, n); return 0; } आउटपुट
The sum of all unique subarray sum is 144
पुनरावृत्ति का उपयोग करके एक अन्य दृष्टिकोण
समस्या को हल करने का एक अन्य दृष्टिकोण हैश टेबल का उपयोग करना है। हम सबएरे योग ढूंढेंगे और उन्हें हैश टेबल में संग्रहीत करेंगे और हैश काउंट बढ़ाएंगे। फिर सभी अद्वितीय सबएरे (हैश काउंट 1 वाले सबएरे) का योग ज्ञात करेंगे।
उदाहरण
हमारे समाधान के कार्य को दर्शाने वाला प्रोग्राम:
#include <bits/stdc++.h> using namespace std; long int findSumOfSubArraySum(int arr[], int n){ int sumSubArraySum = 0; unordered_map<int, int> sumSubArray; for (int i = 0; i < n; i++) { int sum = 0; for (int j = i; j < n; j++) { sum += arr[j]; sumSubArray[sum]++; } } for (auto itr : sumSubArray) if (itr.second == 1) sumSubArraySum += itr.first; return sumSubArraySum; } int main(){ int arr[] = { 1, 2, 4, 7, 5 }; int n = sizeof(arr) / sizeof(arr[0]); cout<<"The sum of all unique subarray sum is "<<findSumOfSubArraySum(arr, n); return 0; } आउटपुट
The sum of all unique subarray sum is 124
