এই আর্টিকেলে আমরা দিয়ে হয়ে রেঞ্জে যোগফল পাওয়া যাবে এমন সাবঅ্যারে সংখ্যা বের করার সমস্যা C++ দিয়ে সমাধান করব। আমাদের একটি পজিটিভ ইন্টিজার (positive integers) অ্যারে 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}।
এই সমস্যা সমাধানের দুটি পদ্ধতি ব্যাখ্যা করা হয়েছে।
সবচেয়ে বেসিক ব্রুট ফোর্স পদ্ধতিতে প্রতিটি সাবঅ্যারের যোগফল বের করে চেক করা হয় সেটি দেওয়া রেঞ্জে আছে কিনা। (কিন্তু এই পদ্ধতিতে অনেক সময় লাগে, টাইম কমপ্লেক্সিটি O(n²) যেখানে n হলো অ্যারে সাইজ)।
সময় বাঁচাতে আমরা অন্য একটি পদ্ধতি ব্যবহার করি যাকে স্লাইডিং উইন্ডো টেকনিক (Sliding Window Technique) বলা হয়। এই টেকনিক দিয়ে আমরা ফলাফল খুব দ্রুত বা দক্ষতার সাথে 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){ // রাইট বর্ডার (end) সরানো sum = sum + arr[end]; while(start <= end && sum >= x){ // লেফ্ট বর্ডার (start) সরানো sum = sum - arr[start]; // লেফ্ট বর্ডার সরানোর সময় সম কমানো // পূর্বের এলিমেন্ট বাদ দিতে start++; // লেফ্ট বর্ডার সরানো } count = count + ((end - start) + 1); // সাবঅ্যারে কাউন্ট 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)); // চূড়ান্ত উত্তর cout << answer << "\n"; return 0; }
3
এই পদ্ধতিতে, আমরা দিয়ে হয়ে রেঞ্জের উপরের লিমিট (upper limit) থেকে কম যোগফল वाले সাবঅ্যারে সংখ্যা বের করি, এবং তারপর নিচের লিমিট (lower limit) থেকে কম যোগফল वाले সাবঅ্যারে সংখ্যা বিয়োগ করি subCount ফাংশন দিয়ে।
এই ফাংশন স্লাইডিং উইন্ডো টেকনিক ব্যবহার করে যোগফল x থেকে কম वाले সাবঅ্যারে কাউন্ট বের করে।
প্রথমে 'end' এবং 'start' উভয় ০ দিয়ে শুরু। অ্যারে ট্রাভার্স করার সময় start থেকে end পর্যন্ত এলিমেন্টের যোগফল মেইনটেইন করা হয়। এরপর, যদি start == end এবং sum >= x হয়, তবে start বড়ায় যাওয়া শুরু হয় এবং sum কমতে থাকে (এলিমেন্ট বাদ দিয়ে)। ততক্ষণ পর্যন্ত sum < x হয় না বা start > end হয় না। এখন কাউন্টে সাবঅ্যারে সংখ্যা যোগ করে end ১ বাড়ানো হয়। বাহিরের লুপ শেষে মোট সাবঅ্যারে কাউন্ট রিটার্ন করা হয়।
এই আর্টিকেলে আমরা স্লাইডিং উইন্ডো টেকনিক দিয়ে O(n) টাইম কমপ্লেক্সিটিতে দিয়ে হয়ে রেঞ্জে যোগফল পাওয়া যাবে এমন সাবঅ্যারে সংখ্যা বের করার সমস্যা সমাধান করেছি। আমরা এই সমস্যার C++ প্রোগ্রাম ও সম্পূর্ণ পদ্ধতি (সহজ ও দক্ষ) দেখেছি। একই প্রোগ্রাম C, Java, Python ইত্যাদি ভাষায়ও লিখা যায়।
