এই সমস্যায়, আমাদেরকে একটি অ্যারে দেওয়া হয়েছে অ্যারে [] যা এন পূর্ণসংখ্যার সমন্বয়ে সংরক্ষিত আছে। আমাদের কাজ হল প্রদত্ত যোগফলের সাথে একটি সাবয়ারে খুঁজে পাওয়া .
সমস্যাটি বোঝার জন্য একটি উদাহরণ নেওয়া যাক,
Input : arr[] = {2, 5, -1, 4, 6, -9, 5} sum = 14
Output : subarray = {5, -1, 4, 6} ব্যাখ্যা −
Subarray sum = 5 - 1 + 4 + 6 = 14
সমাধান পদ্ধতি
সমস্যার একটি সহজ সমাধান হল নেস্টেড লুপ ব্যবহার করা। আমরা অ্যারের মাধ্যমে লুপ করব এবং একটি অভ্যন্তরীণ লুপ ব্যবহার করে, আমরা সাবারে খুঁজে পাব। প্রতিটি সাবয়ারের জন্য আমরা সমস্ত উপাদানের যোগফল খুঁজে বের করব এবং প্রদত্ত যোগফল মানের সাথে তুলনা করব। এটি সমান হলে, subarray মুদ্রণ. যদি অ্যারের সমস্ত উপাদান ট্র্যাভার্স করা হয়, তবে এমন কোনও অ্যারে পাওয়া যায় না।
অ্যালগরিদম
-
ধাপ 1 − অ্যারের মাধ্যমে লুপ করুন, i -> 0 থেকে (n-1)।
-
পদক্ষেপ 1.1৷ − প্রতিটি উপাদানের জন্য, সম্ভাব্য সকল সাবয়ারের জন্য প্রতিটি সাবয়ারের সমষ্টি খুঁজুন।
-
পদক্ষেপ 1.2৷ − যদি বর্তমান সমষ্টি অ্যারের উপাদানগুলির যোগফল প্রদত্ত সাবয়েরের সমান হয়, তাহলে সাব্যারে মুদ্রণ করুন৷
-
-
ধাপ 2 − যদি অ্যারের সমস্ত উপাদান ট্রাভার্স করা হয় এবং কোন সাব্যারে পাওয়া না যায়। প্রিন্ট করুন "প্রদত্ত যোগফলের সাথে কোন সাবয়ারে পাওয়া যায়নি!"।
উদাহরণ
আমাদের সমাধানের কাজ চিত্রিত করার জন্য প্রোগ্রাম
#include <bits/stdc++.h>
using namespace std;
void printSubArray(int arr[], int i, int j){
cout<<"{ ";
for(; i < j; i++)
cout<<arr[i]<<" ";
cout<<"}";
}
int findSubArrayWithSum(int arr[], int n, int sum) {
int currSum;
for (int i = 0; i < n; i++) {
currSum = arr[i];
for (int j = i + 1; j <= n; j++) {
if (currSum == sum) {
cout<<"Subarray with given sum : ";
printSumArray(arr, i, j);
return 1;
}
if (currSum >sum || j == n)
break;
currSum = currSum + arr[j];
}
}
cout<<"No subarray found";
return 0;
}
int main() {
int arr[] = { 2, 5, -1, 4, 6, -9, 3};
int n = sizeof(arr) / sizeof(arr[0]);
int sum = 14;
findSubArrayWithSum(arr, n, sum);
return 0;
} আউটপুট
Subarray with given sum : { 5 -1 4 6 } সমস্যা সমাধানের জন্য একটি ভাল পদ্ধতি হল হ্যাশম্যাপ ব্যবহার করা। হ্যাশম্যাপ বর্তমান সূচক পর্যন্ত উপসর্গের যোগফল সংরক্ষণ করবে। এবং যেকোন সূচকের জন্য, যোগফল সহ একটি সাবয়ারে আছে কিনা তা পরীক্ষা করুন। sum =যোগফল - মান সহ একটি উপসর্গ আছে কিনা তা আমরা পরীক্ষা করব।
উদাহরণ
আমাদের সমাধানের কাজ চিত্রিত করার জন্য প্রোগ্রাম
#include <bits/stdc++.h>
using namespace std;
void printSubArray(int arr[], int i, int j){
cout<<"{ ";
for(; i <= j; i++)
cout<<arr[i]<<" ";
cout<<"}";
}
void findSubArrayWithSum(int arr[], int n, int sum) {
unordered_map<int, int> map;
int curr_sum = 0;
for (int i = 0; i < n; i++){
curr_sum = curr_sum + arr[i];
if (curr_sum == sum) {
cout<<"SubArray with the given sum :";
printSubArray(arr, 0, i);
return;
}
if (map.find(curr_sum - sum) != map.end()) {
cout<<"SubArray with the given sum : ";
printSubArray(arr, map[curr_sum - sum] + 1 , i);
return;
}
map[curr_sum] = i;
}
cout<<"No subarray found!";
}
int main() {
int arr[] = { 2, 5, -1, 4, 6, 9, 3};
int n = sizeof(arr) / sizeof(arr[0]);
int sum = 14;
findSubArrayWithSum(arr, n, sum);
return 0;
} আউটপুট
SubArray with the given sum : { 5 -1 4 6 } 