এই সমস্যায়, আমাদেরকে n পূর্ণসংখ্যার মান সমন্বিত একটি অ্যারে arr[] দেওয়া হয়েছে। আমাদের কাজ হল একটি প্রদত্ত অ্যারের জন্য সমস্ত অনন্য সাবয়ারের যোগফলের যোগফল খুঁজে বের করা . Subarray sum হল প্রদত্ত সাবরের উপাদানের যোগফল।
সমস্যাটি বোঝার জন্য একটি উদাহরণ নেওয়া যাক,
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
পুনরাবৃত্তি ব্যবহার করে আরেকটি পদ্ধতি
সমস্যা সমাধানের আরেকটি পদ্ধতি হল হ্যাশ টেবিল ব্যবহার করা। আমরা সাবয়ারের যোগফল খুঁজে বের করব এবং সেগুলিকে একটি হ্যাশ টেবিলে সংরক্ষণ করব এবং হ্যাশ সংখ্যা বৃদ্ধি করব। তারপরে সমস্ত অনন্য সাবয়ারের সমষ্টি খুঁজুন (হ্যাশ গণনা 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
