सी ++ में दिए गए सरणी के लिए सभी अद्वितीय सबरेरे योग का योग खोजें

इस समस्या में, हमें n पूर्णांक मानों से युक्त एक सरणी arr[] दिया जाता है। हमारा काम किसी दिए गए सरणी के लिए सभी अद्वितीय सबअरे योग का योग ज्ञात करना है . सबअरे योग दिए गए सबअरे के तत्वों का योग है।

समस्या को समझने के लिए एक उदाहरण लेते हैं,

Input : arr[] = {1, 2, 4}
Output : 23

स्पष्टीकरण -

All subarrays of the given array are :
(1), (2), (4), (1, 2), (2, 4), (1, 2, 4)
Sum of subarrays = 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

Iteration का उपयोग करने वाला दूसरा तरीका

समस्या को हल करने का एक और तरीका हैश टेबल का उपयोग करना है। हम सबएरे रकम ढूंढेंगे और उन्हें हैश टेबल और इंक्रीमेंट हैश काउंट में स्टोर करेंगे। फिर सभी अद्वितीय उपसरणियों का योग ज्ञात करें (हैश काउंट 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