যদি কখনো C++ ব্যবহার করে থাকেন, তবে অবশ্যই জানেন সাবঅ্যারে (subarrays) কী এবং কতটা উপকারী। C++-এ আমরা একাধিক গাণিতিক সমস্যা সহজে সমাধান করতে পারি। এই আর্টিকেলে আমরা পূর্ণ তথ্য দেব কিভাবে সাবঅ্যারে দিয়ে m বিজোড় সংখ্যা বের করা যায়।
এই সমস্যায়, আমাদের একটি অ্যারে এবং পূর্ণসংখ্যা m দেওয়া আছে। আমাদের বের করতে হবে কতগুলো সাবঅ্যারে তৈরি করা যায় যাতে প্রতিটি সাবঅ্যারেতে ঠিক m সংখ্যক বিজোড় সংখ্যা (odd numbers) থাকে। সহজ উদাহরণ −
ইনপুট: array = { 6,3,5,8,9 }, m = 2 আউটপুট: 5 ব্যাখ্যা: ঠিক ২টি বিজোড় সংখ্যা 가진 সাবঅ্যারে: {3,5}, {6,3,5}, {3,5,8}, {5,8,9}, {6,3,5,8}, {3,5,8,9}।
ইনপুট: array = { 1,6,3,2,5,4 }, m = 2 আউটপুট: 6 ব্যাখ্যা: সাবঅ্যারে: {1,6,3}, {3,2,5}, {1,6,3,2}, {6,3,2,5}, {3,2,5,4}, {6,3,2,5,4}
এই পদ্ধতিতে, দেওয়া অ্যারেতে থেকে সব সম্ভাব্য সাবঅ্যারে জেনারেট (generate) করে প্রতিটি সাবঅ্যারে চেক করা হয় ঠিক m বিজোড় সংখ্যা আছে কিনা। এটি একটি সহজ জেনারেট অ্যান্ড ফাইন্ড (generate and find) পদ্ধতি, টাইম কমপ্লেক্সিটি O(n²)।
#include <bits/stdc++.h> using namespace std; int main (){ int a[] = { 1, 6, 3, 2, 5, 4 }; int n = 6, m = 2, count = 0; // n=অ্যারে সাইজ, m=খুঁজতে হবে বিজোড় সংখ্যা, count=সাবঅ্যারে সংখ্যা for (int i = 0; i < n; i++){ // বাহিরের লুপ: প্রতিটি এলিমেন্ট প্রসেস int odd = 0; for (int j = i; j < n; j++) { // ভেতরের লুপ: m বিজোড় সাবঅ্যারে খুঁজে if (a[j] % 2) odd++; if (odd == m) count++; // বিজোড় সংখ্যা m হলে কাউন্ট বাড়ানো } } cout << "Number of subarrays with n numbers are: " << count; return 0; }
Number of subarrays with n numbers are: 6
এই কোডে নেস্টেড লুপ (nested loops) ব্যবহার করা হয়েছে sাবঅ্যারে খুঁজে বের করতে m বিজোড় সংখ্যা। বাহিরের লুপ 'i' বড়ায় যা অ্যারের প্রতিটি এলিমেন্ট প্রসেস করে। ভেতরের লুপ সাবঅ্যারে খুঁজে এবং এলিমেন্ট প্রসেস করে যতক্ষণ না odd কাউন্টার m-এ পৌঁছায়, প্রতিটি সাবঅ্যারে পাওয়ার জন্য result কাউন্টার (count) বাড়ানো হয়। শেষে count ভেরিয়েবলে সংরক্ষিত ফলাফল প্রিন্ট করা হয়।
অন্য একটি পদ্ধতিতে, একটি প্রিফিক্স অ্যারে (prefix array) তৈরি করা হয় 'i' বিজোড় সংখ্যা वाले প্রিফিক্সের (prefix) সংখ্যা রাখতে। প্রতিটি এলিমেন্ট প্রসেস করা হয় এবং বিজোড় সংখ্যা পাওয়া গেলে odd কাউন্টার বাড়ানো হয়।
যখন বিজোড় সংখ্যা m-এর সমান বা বেশি হয়, তবে প্রিফিক্স অ্যারেতে (odd - m) পজিশনের মান যোগ করা হয়। যখন odd >= m হয়, তখন ইনডেক্স পর্যন্ত বने সাবঅ্যারে সংখ্যা এবং "odd - m" সংখ্যা কাউন্ট ভেরিয়েবলে যোগ করা হয়। শেষে সব এলিমেন্ট প্রসেস হলে কাউন্ট ভেরিয়েবলে ফলাফল থাকে।
#include <bits/stdc++.h> using namespace std; int main (){ int array[ ] = { 1, 6, 3, 2, 5, 4 }; int n = 6, m = 2, count = 0, odd = 0, i; int prefix_array[n + 1] = { 0 }; // প্রতিটি এলিমেন্ট প্রসেস করার বাহিরের লুপ for (i = 0; i < n; i++){ prefix_array[odd] = prefix_array[odd] + 1; // odd ইনডেক্সে ভ্যালু ইনসার্ট // এলিমেন্ট বিজোড় হলে odd বাড়ানো if (array[i] % 2 == 0) odd++; // বিজোড় সংখ্যা m-এর সমান বা বেশি হলে // ইনডেক্স পর্যন্ত বने সম্ভাব্য সাবঅ্যারে সংখ্যা বের করা if (odd >= m) count += prefix_array[odd - m]; } cout << "Number of subarrays with n numbers are: " << count; return 0; }
Number of subarrays with n numbers are: 6
অ্যারে এবং ভেরিয়েবল ইনিশিয়ালাইজেশন −
int array[6] = { 1, 6, 3, 2, 5, 4 }; int n = 6, m = 2, count = 0, odd = 0, i; int prefix_array[n + 1] = { 0 };
এখানে n=অ্যারে সাইজ, m=খুঁজতে হবে বিজোড় সংখ্যা, count=সাবঅ্যারে কাউন্ট, odd=০, prefix_array সাইজ n+1, সব ০।
for (i = 0; i < n; i++){ prefix_array[odd] = prefix_array[odd] + 1; if (array[i] % 2 == 0) odd++; if (odd >= m) count += prefix_array[odd - m]; }
এই লুপে, odd ইনডেক্সে prefix_array-এ ভ্যালু ইনসার্ট করা হয়েছে, তারপর বিজোড় সংখ্যা পাওয়া গেলে odd বাড়ানো হয়েছে। odd >= m হলে ইনডেক্স পর্যন্ত বने সাবঅ্যারে সংখ্যা বের করা হয়েছে।
শেষে m বিজোড় সংখ্যা 가진 সাবঅ্যারে সংখ্যা count ভেরিয়েবলে থাকা ফলাফল প্রিন্ট করা হয়েছে।
এই আর্টিকেলে আমরা m বিজোড় সংখ্যা 가진 সাবঅ্যারে সংখ্যা বের করার দুটি পদ্ধতি বুঝেছি −
প্রতিটি সাবঅ্যারে জেনারেট করে m বিজোড় সংখ্যা চেক করা এবং পাওয়া গেলে কাউন্ট বাড়ানো। টাইম কমপ্লেক্সিটি O(n²)।
দক্ষ পদ্ধতি: প্রতিটি এলিমেন্ট প্রসেস করে প্রিফিক্স অ্যারে তৈরি করে এবং প্রিফিক্স অ্যারের সাহায্যে ফলাফল বের করা। টাইম কমপ্লেক্সিটি O(n)।
আশা করি এই আর্টিকেলটি সমস্যা ও সমাধান বোঝাতে সহায়ক হবে।
