এই সমস্যায়, আমাদের একটি অ্যারে 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
সমাধানের পদ্ধতি
এই সমস্যার সমাধান হল সাবঅ্যারে যোগফলগুলো সংরক্ষণ করা এবং তারপর সেগুলো সর্ট করে উনিক গুলো খুঁজে বের করা। তারপর আমরা সব উনিক সাবঅ্যারেগুলো বিবেচনা করব যোগফলের জন্য।
অ্যালগরিদম
স্টেপ ১ − সব সাব-অ্যারেতার যোগফল বের করে একটি ভেক্টরে সংরক্ষণ করুন।
স্টেপ ২ − ভেক্টরটি সর্ট করুন।
স্টেপ ৩ − যেসব ভেক্টর উনিক তা বিবেচনা করুন এবং বাকিদের যোগফল ০ করে দিন।
স্টেপ ৪ − যোগফল ক্যালকুলেট করে প্রিন্ট করুন।
উদাহরণ প্রোগ্রাম (সর্টিং পদ্ধতি)
আমাদের সমাধানের কাজকাণ্ড ব্যাখ্যা করার প্রোগ্রাম:
#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
আরেকটি পদ্ধতি (হ্যাশ টেবিল ব্যবহার করে)
এই সমস্যা সমাধানের আরেকটি পদ্ধতি হল হ্যাশ টেবিল ব্যবহার করা। আমরা সাবঅ্যারে যোগফলগুলো বের করব এবং সেগুলো হ্যাশ টেবিলে সংরক্ষণ করব এবং হ্যাশ কাউন্ট বাড়াব। তারপর সব উনিক সাবঅ্যারেগুলোর (হ্যাশ কাউন্ট ১ olan সাবঅ্যারে) যোগফল বের করব।
উদাহরণ প্রোগ্রাম (হ্যাশ টেবিল পদ্ধতি)
#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
