এই নিবন্ধে, আমরা C++ প্রোগ্রাম ব্যবহার করে একটি প্রদত্ত পরিসরে যোগফল সহ সাবয়ারের সংখ্যা সমাধান করব। আমাদের কাছে ধনাত্মক পূর্ণসংখ্যাগুলির একটি অ্যারে অ্যারে [] আছে, এবং একটি পরিসর {L, R} এবং আমাদেরকে প্রদত্ত রেঞ্জ ফর্ম L থেকে R-এর মধ্যে যোগফল সহ মোট সাব্যারেগুলির সংখ্যা গণনা করতে হবে। তাই এখানে সমস্যার সহজ উদাহরণ হল −
Input : arr[] = {1, 4, 6}, L = 3, R = 8
Output : 3
The subarrays are {1, 4}, {4}, {6}.
Input : arr[] = {2, 3, 5, 8}, L = 4, R = 13
Output : 6
The subarrays are {2, 3}, {2, 3, 5}, {3, 5},
{5}, {5, 8}, {8}. সমাধান খোঁজার পন্থা
আমরা C++ সমস্যা −
ব্যবহার করে এই সমস্যাটি সমাধান করার জন্য দুটি পদ্ধতি ব্যাখ্যা করবব্রুট ফোর্স অ্যাপ্রোচ
সবথেকে বেসিক ব্রুট ফোর্স অ্যাপ্রোচ ব্যবহার করা হয় প্রতিটি সাবয়ারের যোগফল গণনা করতে এবং তারপর সেই যোগফলটি প্রদত্ত পরিসরে আছে কি না তা খুঁজে বের করতে। (কিন্তু এই পদ্ধতির জন্য আমাদের অনেক সময় ব্যয় হবে কারণ এর সময় জটিলতা হল O(n*n) যেখানে n হল অ্যারের আকার)।
দক্ষ পদ্ধতি
সময় বাঁচানোর জন্য, আমরা অন্য একটি পদ্ধতি ব্যবহার করি যা একটি দক্ষ পন্থা হিসাবে পরিচিত৷ এখন দক্ষ পদ্ধতি হল স্লাইডিং উইন্ডো কৌশল ব্যবহার করে, এই কৌশলটি ব্যবহার করে আমরা আমাদের ফলাফলগুলি O(n) এ অনেক দ্রুত বা দক্ষতার সাথে গণনা করব৷
উদাহরণ
#include <bits/stdc++.h>
using namespace std;
int subCount(int *arr, int n, int x){
int start = 0, end = 0, sum = 0, count = 0;
while (end < n){ // we will be moving right border in this loop
sum = sum + arr[end];
while(start <= end && sum >= x){ // this loop will move our left border
sum = sum - arr[start]; // we will decrement sum while moving left border.
// For excluding the previous elements.
start++; // and move the left border.
}
count = count + ((end - start) + 1); // counting the subarrays.
end++;
}
return count;
}
int main(){
int arr[] = { 1, 4, 6 };
int n = sizeof(arr) / sizeof(arr[0]);
int L = 3;
int R = 8;
int answer;
answer = subCount(arr, n, R) - subCount(arr, n, (L - 1)); // Final Answer.
cout << answer << "\n";
return 0;
} আউটপুট
3
উপরের কোডের ব্যাখ্যা
এই পদ্ধতিতে, আমরা প্রদত্ত পরিসরের উপরের সীমার চেয়ে কম যোগফল সহ সাবয়ারের সংখ্যা গণনা করছি, এবং তারপরে আমরা আমাদের সাবকাউন্ট ফাংশন ব্যবহার করে আমাদের প্রদত্ত পরিসরের নিম্ন সীমার থেকে কম সাব্যারেগুলির সংখ্যা বিয়োগ করছি।
সাবকাউন্ট ফাংশন
এই ফাংশনটি স্লাইডিং উইন্ডো কৌশল ব্যবহার করে সাবয়ারের গণনা খুঁজে বের করার জন্য যার সংখ্যা x এর চেয়ে কম।
প্রথমে, আমরা 'শেষ এবং শুরু' উভয়ই তাদের মান হিসাবে 0 দিয়ে শুরু করি। আমরা অ্যারে অতিক্রম করার সময়, আমরা শুরু থেকে শেষ পর্যন্ত উপাদানগুলির যোগফল বজায় রাখি। এর পরে, যদি আমাদের শুরু আমাদের শেষের সমান হয় এবং যোগফল x এর চেয়ে বড় বা সমান হয়, আমরা আমাদের শুরুকে সরাতে শুরু করি এবং যোগফল থেকে উপাদানগুলি সরিয়ে নেওয়ার সাথে সাথে আমাদের যোগফল কমাতে থাকি।
যতক্ষণ না আমাদের যোগফল x এর থেকে কম হয় বা আমাদের শুরু শেষের চেয়ে বড় হয়। এখন আমরা সাবয়ারের গণনা দ্বারা গণনা বৃদ্ধি করি এবং তারপর 1 দিয়ে ডান সীমানা বৃদ্ধি করি। এখন, আমাদের বাইরের লুপ শেষ হওয়ার পরে, আমরা আমাদের সাবয়ারের মোট গণনা ফেরত দিই।
উপসংহার
এই নিবন্ধে, আমরা স্লাইডিং উইন্ডো কৌশল ব্যবহার করে O(n) সময় জটিলতায় একটি প্রদত্ত পরিসরে যোগফল থাকা সাবয়ারের সংখ্যা খুঁজে বের করার জন্য একটি সমস্যার সমাধান করি। আমরা এই সমস্যার জন্য C++ প্রোগ্রাম এবং সম্পূর্ণ পদ্ধতি (স্বাভাবিক এবং দক্ষ) থেকে শিখেছি যার মাধ্যমে আমরা সহজেই এই সমস্যার সমাধান করতে পারি। আমরা একই প্রোগ্রাম অন্যান্য ভাষায় লিখতে পারি যেমন সি, জাভা, পাইথন ইত্যাদি।
