এই সমস্যায়, আমাদেরকে পূর্ণসংখ্যার মান সমন্বিত n আকারের একটি অ্যারে দেওয়া হয়েছে। আমাদের কাজ হল 0 যোগ সহ একটি সাবয়ারে আছে কিনা তা খুঁজে বের করা।
প্রদত্ত অ্যারেটিতে একটি সাব-অ্যারে রয়েছে কিনা তা আমাদের পরীক্ষা করতে হবে যেখানে সমস্ত উপাদানের যোগফল 0 এর সমান।
সমস্যাটি বোঝার জন্য একটি উদাহরণ নেওয়া যাক,
ইনপুট: arr[] ={3, 1, -2, 1, 4, 5}
আউটপুট: হ্যাঁ
ব্যাখ্যা:
সাবারে {1, -2, 1}-এ 0 এর সমান সমস্ত মানের যোগফল রয়েছে৷
সমাধান পদ্ধতি:
সমস্ত সাবঅ্যারে বিবেচনা করে এবং সমস্ত উপাদানের যোগফল 0 এর সমান চেক করে সমস্যার একটি সহজ সমাধান৷
সমস্যার আরেকটি সমাধান হল হ্যাশিং ব্যবহার করে। আমাদের অ্যারে লুপ করতে হবে এবং তারপর বর্তমান সূচক পর্যন্ত যোগফল খুঁজে বের করতে হবে এবং হ্যাশ টেবিলে সংরক্ষণ করতে হবে।
তারপর হ্যাশ টেবিলে চেক করুন, যদি যোগফলের মান পূর্বের সম্মুখীন হয় তাহলে যোগফল =0 সহ একটি সাবয়ারে পাওয়া যায়।
সাবারে পাওয়া গেলে True ফেরত দিন
অন্যথায় মিথ্যা ফেরত দিন
আমাদের সমস্যার কাজ চিত্রিত করার জন্য প্রোগ্রাম,
উদাহরণ
#include <bits/stdc++.h>
using namespace std;
bool isSubArraySumZero(int arr[], int n) {
unordered_set<int> sumHash;
int currSum = 0;
for (int i = 0 ; i < n ; i++) {
currSum += arr[i];
if (currSum == 0 || sumHash.find(currSum) != sumHash.end())
return true;
sumHash.insert(currSum);
}
return false;
}
int main() {
int arr[] = { 3, 1, -2, 1, 4, 5 };
int n = sizeof(arr)/sizeof(arr[0]);
if (isSubArraySumZero(arr, n))
cout<<"SubArray with sum equal to 0 exists in the array";
else
cout<<"No subarray exists";
return 0;
} আউটপুট
SubArray with sum equal to 0 exists in the array
