এই সমস্যায়, একটি ইন্টিজার অ্যারে দেওয়া থাকে এবং আমাদের সেই সাবঅ্যারেগুলো প্রিন্ট করতে হবে যাদের যোগফল ০।
উদাহরণ দিয়ে বুঝি:
ইনপুট: array = [-5, 0, 2, 3, -3, 4, -1] আউটপুট: Subarray with sum 0 is from 1 to 4. Subarray with sum 0 is from 5 to 7 Subarray with sum 0 is from 0 to 7
এই সমস্যাটি সমাধান করার জন্য, আমরা সব সম্ভাব্য সাবঅ্যারে চেক করব। এবং চেক করব এই সাবঅ্যারেগুলোর যোগফল ০ কিনা এবং প্রিন্ট করব। এই সমাধানটি বোঝা সহজ কিন্তু জটিল, এবং এর টাইম কমপ্লেক্সিটি O(n²)।
এই সমস্যাটির একটি আরও ভালো সমাধান হলো হ্যাশিং ব্যবহার করা। এতে আমরা যোগফল খুঁজে বের করব, যদি সেটি ০ সমান হয় তবে হ্যাশ টেবিলে যোগ করব।
অ্যালগরিদম
ধাপ ১: একটি sum ভেরিয়েবল তৈরি করুন। ধাপ ২: যদি sum = 0 হয়, সাবঅ্যারে শুরু হয় ইনডেক্স ০ থেকে আয়ের cuốiের ইনডেক্স পর্যন্ত। ধাপ ৩: যদি করেন্ট sum হ্যাশ টেবিলে থাকে। ধাপ ৪: যদি sum থাকে, তবে i+1 থেকে n পর্যন্ত সাবঅ্যারে শূন্য হবে। ধাপ ৫: অন্যথায় হ্যাশ টেবিলে ইনসার্ট করুন।
C++ উদাহরণ
#include <bits/stdc++.h> using namespace std; vector< pair<int, int> > findSubArrayWithSumZero(int arr[], int n){ unordered_map<int, vector<int> >map; vector <pair<int, int>> out; int sum = 0; for (int i = 0; i < n; i++){ sum += arr[i]; if (sum == 0) out.push_back(make_pair(0, i)); if (map.find(sum) != map.end()){ vector<int> vc = map[sum]; for (auto it = vc.begin(); it != vc.end(); it++) out.push_back(make_pair(*it + 1, i)); } map[sum].push_back(i); } return out; } int main(){ int arr[] = {-5, 0, 2, 3, -3, 4, -1}; int n = sizeof(arr)/sizeof(arr[0]); vector<pair<int, int> > out = findSubArrayWithSumZero(arr, n); if (out.size() == 0) cout << "No subarray exists"; else for (auto it = out.begin(); it != out.end(); it++) cout<<"Subarray with sum 0 is from "<<it->first <<" to "<<it->second<<endl; return 0; }আউটপুট
Subarray with sum 0 is from 1 to 1 Subarray with sum 0 is from 0 to 3 Subarray with sum 0 is from 3 to 4 Subarray with sum 0 is from 0 to 6 Subarray with sum 0 is from 4 to 6
