এই সমস্যায়, আমাদের একটি অ্যারে arr[] দেওয়া আছে যাতে N সংখ্যক পজিটিভ ইন্টিজার আনসর্টেড অর্ডারে সংরক্ষিত। আমাদের কাজ হল দেওয়া যোগফলযুক্ত একটি সাবঅ্যারে খুঁজে বের করা।
উদাহরণ
সমস্যাটি বুঝতে একটি উদাহরণ নিই:
ইনপুট : arr[] = {2, 5, 1, 4, 6, 9, 5} sum = 11
আউটপুট : subarray = {1, 4, 6}
ব্যাখ্যা:
সাবঅ্যারে যোগফল = 1 + 4 + 6 = 11
সমাধানের পদ্ধতি
এই সমস্যার একটি সহজ সমাধান হল নেস্টেড লুপ ব্যবহার করা। আমরা অ্যারেতে লুপ চালাব এবং ইনার লুপ দিয়ে সাবঅ্যারে খুঁজে বের করব। প্রতিটি সাবঅ্যারেতে সব উপাদানের যোগফল বের করে দেওয়া যোগফলের সাথে তুলনা করব। যদি সমান হয়, সাবঅ্যারেটি প্রিন্ট করব। যদি পুরো অ্যারে ট্রাভার্স হয়ে যায়, তবে প্রিন্ট করব যে এরকম কোনো অ্যারে পাওয়া যায়নি।
অ্যালগরিদম
স্টেপ ১ − অ্যারেতে লুপ চালান, i → 0 থেকে (n-1) পর্যন্ত।
স্টেপ ১.১ − প্রতিটি উপাদানের জন্য, সব সম্ভাব্য সাবঅ্যারেতের যোগফল বের করুন।
স্টেপ ১.২ − যদি বর্তমান সাবঅ্যারে উপাদানগুলোর যোগফল দেওয়া সাবঅ্যারের সমান হয়, তবে সাবঅ্যারেটি প্রিন্ট করুন।
স্টেপ ২ − যদি অ্যারেতার সব উপাদান ট্রাভার্স হয়ে যায় এবং কোনো সাবঅ্যারে না পাওয়া যায়। "No subarray with the given sum found!" প্রিন্ট করুন।
উদাহরণ প্রোগ্রাম (নেস্টেড লুপ পদ্ধতি)
আমাদের সমাধানের কাজকাণ্ড ব্যাখ্যা করার প্রোগ্রাম:
#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 : ";
printSubArray(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 = 11;
findSubArrayWithSum(arr, n, sum);
return 0;
}
আউটপুট
Subarray with given sum : { 1 4 6 }
উন্নত পদ্ধতি (স্লাইডিং উইন্ডো পদ্ধতি)
এই সমস্যা সমাধানের একটি ভালো পদ্ধতি হল স্লাইডিং উইন্ডোর অনুরূপ একটি পদ্ধতি ব্যবহার করা কিন্তু এখানে আমাদের একটি ভেরিয়েবল উইন্ডো থাকবে। আমরা অ্যারেতার প্রথম উপাদান থেকে শুরু করব, উইন্ডোতে উপাদান যোগ করব যতক্ষণ না যোগফল দেওয়া যোগফলের চেয়ে বড় হয়। যদি বড় হয়, তবে উইন্ডোর আকার ছোট করব উপাদান বাদ দিয়ে যতক্ষণ না যোগফল আবার ছোট হয়। এই প্রক্রিয়া পুরো অ্যারে ট্রাভার্স হওয়া পর্যন্ত চলবে।
যদি কোনো মুহূর্তে উইন্ডোর যোগফল দেওয়া যোগফলের সমান হয়, তবে সাবঅ্যারেটি প্রিন্ট করব। এবং যদি কোনো উইন্ডোর যোগফল দেওয়া যোগফলের সমান না হয় এবং ট্রাভার্স করার জন্য কোনো উপাদান না থাকে, তবে "No subarray found!" প্রিন্ট করব।
অ্যালগরিদম
ইনিশিয়ালাইজ − windowSum = 0, sindex = 0, endindex = 0
স্টেপ ১ − endIndex ব্যবহার করে অ্যারে ট্রাভার্স করুন।
স্টেপ ১.১ − উইন্ডো সাম যোগফল আপডেট করুন উপাদান যোগ করে যতক্ষণ না উইন্ডো সাম দেওয়া যোগফলের চেয়ে বড় হয়।
স্টেপ ১.২ − যদি উইন্ডো সাম দেওয়া যোগফলের চেয়ে বড় হয়, উইন্ডোর আকার ছোট করুন উপাদান বাদ দিয়ে।
স্টেপ ১.৩ − যদি windowSum == sum হয়, সাবঅ্যারে প্রিন্ট করুন।
স্টেপ ২ − যদি অ্যারে ট্রাভার্স হয়ে যায়, প্রিন্ট করুন → 'not possible'।
উদাহরণ প্রোগ্রাম (স্লাইডিং উইন্ডো পদ্ধতি)
#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 windowSum = arr[0], startIndex = 0, endIndex;
for (endIndex = 1; endIndex <= n; endIndex++) {
while (windowSum > sum && startIndex < endIndex - 1) {
windowSum -= arr[startIndex];
startIndex++;
}
if (windowSum == sum) {
cout << "Subarray with given sum : ";
printSubArray(arr, startIndex, endIndex);
return 1;
}
if (endIndex < n)
windowSum += arr[endIndex];
}
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 = 11;
findSubArrayWithSum(arr, n, sum);
return 0;
}
আউটপুট
Subarray with given sum : { 1 4 6 }
