এই আর্টিকেলে আমরা C++ ব্যবহার করে K-এর চেয়ে কম যোগফল والے সাবঅ্যারে সংখ্যা বের করার পদ্ধতি আলোচনা করব। এখানে একটি অ্যারে arr[] এবং একটি পূর্ণসংখ্যা K দেওয়া আছে। আমাদের কাজ হল সেই সাবঅ্যারেগুলো খুঁজে বের করা যাদের উপাদানগুলোর যোগফল K-এর চেয়ে কম। নিচে একটি উদাহরণ দেওয়া হলো:
ইনপুট : arr[] = {1, 11, 2, 3, 15} K = 10
আউটপুট : 4
{1}, {2}, {3} এবং {2, 3}
সমাধানের পদ্ধতি
এই সমস্যাটি সমাধানের জন্য আমরা দুটি ভিন্ন পদ্ধতি ব্যবহার করব:
ব্রুট ফোর্স পদ্ধতি
এই পদ্ধতিতে আমরা সকল সম্ভাব্য সাবঅ্যারে এর মাধ্যমে পুনরাবৃত্তি করব, তাদের যোগফল হিসাব করব এবং যদি যোগফল K-এর চেয়ে কম হয় তবে আমাদের কাউন্টার বাড়াব।
উদাহরণ
#include <bits/stdc++.h> using namespace std; int main(){ int arr[] = {1, 11, 2, 3, 15}; // দেওয়া অ্যারে int k = 10; // দেওয়া k int size = sizeof(arr) / sizeof(int); // অ্যারের আকার int ans = 0; // কাউন্টার ভেরিয়েবল for(int i = 0; i < size; i++){ // বাহ্যিক লুপ int sum = 0; for(int j = i; j < size; j++){ // অভ্যন্তরিন লুপ sum = sum + arr[j]; if(sum < k) // k-এর সাথে তুলনা ans++; // যোগফল k-এর চেয়ে কম হলে ans বাড়ানো } } cout << ans << "\n"; return 0; }
আউটপুট
4
তবে এই পদ্ধতিটি কার্যকর নয় কারণ এর সময় জটিলতা খুব বেশি O(N²), যেখানে N হল অ্যারের আকার।
এখন আমরা একটি বিকল্প সমাধান দেখব যেটি স্লাইডিং উইন্ডো পদ্ধতি ব্যবহার করে (এটি প্রোগ্রামের সময় জটিলতা কমাতে সাহায্য করবে)।
দক্ষ পদ্ধতি (Efficient Approach)
ব্রুট ফোর্স-এর বিপরীতে, এখানে আমরা সকল সাবঅ্যারে traverser করব না। বরং আমরা তখনই traverser করব যখন একটি সাবঅ্যারের যোগফল K-এর চেয়ে বড় হয় এবং আমাদের বাম সীমাকে ডান সীমার দিকে সরিয়ে আনার আগামী পর্যন্ত প্রক্রিয়াটি চলবে।
উদাহরণ
#include <bits/stdc++.h> using namespace std; int main(){ int arr[] = {1, 11, 2, 3, 15}; // দেওয়া অ্যারে int k = 10; // দেওয়া k int size = sizeof(arr) / sizeof(int); // অ্যারের আকার int ans = 0; // কাউন্টার ভেরিয়েবল int start = 0; // বাম সীমা int end = 0; // ডান সীমা int sum = 0; while(end < size && start < size){ // পুরো অ্যারে traverser না হওয়া পর্যন্ত while(sum >= k && start < end){ sum = sum - arr[start]; start++; } if(end >= start) ans = ans + end - start; sum += arr[end]; end++; } cout << ans << "\n"; return 0; }
আউটপুট
4
এই পদ্ধতিতে আমরা স্লাইডিং উইন্ডো কৌশল ব্যবহার করি যাতে বড় ইনপুটের জন্যও প্রোগ্রাম দ্রুত চলে।
উপরোক্ত কোডের ব্যাখ্যা
এই পদ্ধতিতে আমরা সাধারণভাবে traverser করি যতক্ষণ না যোগফল K-এর চেয়ে কম, এবং সেই অনুযায়ী আউটপুট বাড়াই। কোডের গুরুত্বপূর্ণ পরিবর্তন ঘটে যখন যোগফল K-এর চেয়ে বড় বা সমান হয়। সেক্ষেত্রে আমরা বাম সীমাকে ডান সীমার দিকে বা যোগফল K-এর চেয়ে কম হওয়া পর্যন্ত সরিয়ে আনি। এভাবে নতুন সাবঅ্যারেগুলো প্রক্রিয়া হয় যাদের যোগফল K-এর চেয়ে কম, এবং সেগুলো আউটপুটে যোগ হয়।
ব্রুট ফোর্স পদ্ধতির তুলনায় এই পদ্ধতি খুব দক্ষ কারণ এর সময় জটিলতা O(N), যেখানে N হল অ্যারের আকার।
উপসংহার
এই আর্টিকেলে আমরা স্লাইডিং উইন্ডো কৌশল ব্যবহার করে K-এর চেয়ে কম যোগফল वाले সাবঅ্যারে সংখ্যা বের করার সমস্যা সমাধান করেছি। আমরা এই সমস্যার জন্য C++ প্রোগ্রাম এবং পূর্ণ পদ্ধতি (সাধারণ এবং দক্ষ) শিখেছি। একই প্রোগ্রামটি C, Java, Python বা অন্য ভাষায়ও লেখা যায়। আশা করি এই আর্টিকেলটি আপনার জন্য সহায়ক হবে।
