এই আর্টিকেলে আমরা C++ প্রোগ্রাম ব্যবহার করে প্রদত্ত রেঞ্জের মধ্যে যোগফল वाले সাবঅ্যারে সংখ্যা বের করব। আমাদের কাছে একটি ধনাত্মক পূর্ণসংখ্যার অ্যারে arr[] এবং একটি রেঞ্জ {L, R} আছে। আমাদের কাজ হল L থেকে R পর্যন্ত যোগফল वाले সাবঅ্যারে মোট কতটি আছে সেটি বের করা। নিচে সহজ উদাহরণ দেওয়া হলো:
ইনপুট : arr[] = {1, 4, 6}, L = 3, R = 8
আউটপুট : 3
সাবঅ্যারেগুলো হল {1, 4}, {4}, {6}।
ইনপুট : arr[] = {2, 3, 5, 8}, L = 4, R = 13
আউটপুট : 6
সাবঅ্যারেগুলো হল {2, 3}, {2, 3, 5}, {3, 5}, {5}, {5, 8}, {8}।
সমাধানের পদ্ধতিসমূহ
এই সমস্যাটি C++-এ সমাধানের জন্য আমরা দুটি পদ্ধতি ব্যাখ্যা করব:
ব্রুট ফোর্স পদ্ধতি
সবচেয়ে সহজ ব্রুট ফোর্স পদ্ধতিতে প্রতিটি সাবঅ্যারের যোগফল বের করে চেক করা হয় যে সেটি দেওয়া রেঞ্জের মধ্যে আছে কিনা। (কিন্তু এই পদ্ধতিটি অনেক সময় নেয় কারণ এর সময় জটিলতা O(n²), যেখানে n হল অ্যারের আকার)।
দক্ষ পদ্ধতি (Efficient Approach)
সময় বাঁচাতে আমরা স্লাইডিং উইন্ডো কৌশল ব্যবহার করব, যা 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){ // ডান সীমা সরাব sum = sum + arr[end]; while(start <= end && sum >= x){ // বাম সীমা সরাব sum = sum - arr[start]; // বাম সীমা সরানোর সাথে যোগফল কমাব start++; } count = count + ((end - start) + 1); // সাবঅ্যারে গণনা end++; } return count; } int main(){ int n; // অ্যারের আকার int L, R; cin >> n; int arr[n]; for(int i = 0; i < n; i++) cin >> arr[i]; cin >> L >> R; int answer; answer = subCount(arr, n, R) - subCount(arr, n, (L - 1)); // চূড়ান্ত উত্তর cout << answer << "\n"; return 0; }
আউটপুট
1
উপরোক্ত কোডের ব্যাখ্যা
এই পদ্ধতিতে আমরা প্রদত্ত রেঞ্জের উপরের সীমা (R) এর চেয়ে কম যোগফল वाले সাবঅ্যারে সংখ্যা বের করি, তারপর রেঞ্জের নিচের সীমা (L) এর চেয়ে কম যোগফল वाले সাবঅ্যারে সংখ্যা বিয়োগ করি subCount ফাংশন ব্যবহার করে।
subCount ফাংশন
এই ফাংশনটি স্লাইডিং উইন্ডো কৌশল ব্যবহার করে x-এর চেয়ে কম যোগফল वाले সাবঅ্যারে সংখ্যা বের করে।
প্রথমে start এবং end দুটোই 0 থেকে শুরু হয়। অ্যারে traverser করার সময় আমরা start থেকে end পর্যন্ত উপাদানগুলোর যোগফল রেখে চলি। এরপর যদি start बरাবর end হয় এবং যোগফল x-এর চেয়ে বড় বা সমান হয়, তবে আমরা start বড় করি এবং যোগফল থেকে উপাদান বাদ দিই। এটি তখন পর্যন্ত চলবে যতক্ষণ না যোগফল x-এর চেয়ে কম হয় বা start > end হয়। এখন সাবঅ্যারে সংখ্যা যোগ করে end-কে 1 বাড়াই। বাহ্যিক লুপ শেষ হলে মোট সাবঅ্যারে সংখ্যা রিটার্ন করি।
উপসংহার
এই আর্টিকেলে আমরা স্লাইডিং উইন্ডো কৌশল ব্যবহার করে O(n) সময় জটিলতায় প্রদত্ত রেঞ্জের মধ্যে যোগফল वाले সাবঅ্যারে সংখ্যা বের করার সমস্যা সমাধান করেছি। আমরা C++ প্রোগ্রাম এবং সম্পূর্ণ পদ্ধতি (সাধারণ এবং দক্ষ) শিখেছি। একই প্রোগ্রাম C, Java, Python ইত্যাদিতে লেখা যায়।
