এই সমস্যায়, আমাদের একটি পূর্ণসংখ্যা অ্যারে দেওয়া আছে। আমাদের কাজ হল শূন্য যোগফলযুক্ত যেকোনো সাবঅ্যারে আছে কিনা তা খুঁজে বের করা।
আমাদের যাচাই করতে হবে যে দেওয়া অ্যারেতে এমন কোনো সাবঅ্যারে আছে কিনা যার সব এলিমেন্টের যোগফল ০।
উদাহরণ দিয়ে বুঝি,
ইনপুট: arr[] = {3, 1, -2, 1, 4, 5}
আউটপুট: হ্যাঁ
ব্যাখ্যা:
সাবঅ্যারে {1, -2, 1}-এর সব মান যোগ করলে ০ হয়।
সমাধানের পদ্ধতি:
সরল সমাধান হল সব সাবঅ্যারে বিবেচনা করে তাদের যোগফল ০ কিনা যাচাই করা। আর একটি দক্ষ সমাধান হল হ্যাশিং ব্যবহার করা। আমরা অ্যারে লুপ করব এবং বর্তমান ইন্ডেক্স পর্যন্ত যোগফল বের করে হ্যাশ টেবিলে রাখব। তারপর হ্যাশ টেবিলে দেখব, আগে একই যোগফল পাওয়া গেলে শূন্য যোগফলযুক্ত সাবঅ্যারে 있다는 মানে।
- সাবঅ্যারে পাওয়া গেলে True রিটার্ন করুন।
- অন্যথায় False রিটার্ন করুন।
সমাধান দর্শানোর প্রোগ্রাম,
উদাহরণ
#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
