সাবঅ্যারে (Subarrays) হলো একটি অ্যারের সन्नিহিত অংশ (contiguous part)। উদাহরণস্বরূপ, অ্যারে [5, 6, 7, 8] নিলে দশটি নন-এম্পটি সাবঅ্যারে বানাবে: (5), (6), (7), (8), (5, 6), (6,7), (7,8), (5,6,7), (6,7,8) এবং (5,6,7,8)।
এই গাইডে, আমরা C++-এ বিজোড় যোগফল (odd sum) والے সাবঅ্যারের সংখ্যা বের করার সব সম্ভাব্য তথ্য ব্যাখ্যা করব। এখানে একটি সহজ উদাহরণ −
ইনপুট: array = {9, 8, 7, 6, 5} আউটপুট: 9 ব্যাখ্যা: বিজোড় যোগফল वाले সাবঅ্যারে: {9}=9, {7}=7, {5}=5, {9,8}=17, {8,7}=15, {7,6}=13, {6,5}=11, {8,7,6}=21, {9,8,7,6,5}=35
এই পদ্ধতিতে, আমরা সব সাবঅ্যারের এলিমেন্টের যোগফল জোড় নাকি বিজোড় চেক করব। বিজোড় হলে কাউন্ট করব, জোড় হলে রিজেক্ট (reject) করব। এটি দক্ষ পদ্ধতি নয় কারণ এর টাইম কমপ্লেক্সিটি O(n²)।
#include <bits/stdc++.h> using namespace std; int main(){ int n=5, temp = 0; int a[n-1] = { 9,8,7,6,5 } ; // অ্যারে ডিক্লেয়ার int cnt = 0; // কাউন্টার ভেরিয়েবল for(int i = 0; i < n; i++){ temp = 0; // টেম্প সম রিফ্রেশ for(int j = i; j < n; j++){ // i থেকে n-1 পর্যন্ত সাবঅ্যারে temp = temp + a[j]; if( temp % 2 == 1 ) cnt++; } } cout << "Number of subarrays with odd sum : " << cnt << "\n"; return 0; }
Number of subarrays with odd sum : 9
এই কোডে নেস্টেড লুপ (nested loops) ব্যবহার করা হয়েছে। বাহিরের লুপ i বড়ায় যা অ্যারের প্রতিটি এলিমেন্টকে পয়েন্ট করে; ভেতরের লুপ i পজিশন থেকে শুরু হয়ে বিজোড় যোগফল वाले সাবঅ্যারে খুঁজে বের করে।
এই পদ্ধতিতে, আমরা অ্যারের ০-তম পজিশন থেকে প্রতিটি এলিমেন্ট প্রসেস করব। যদি করেন্ট এলিমেন্ট বিজোড় হয়, তবে বিজোড় কাউন্টার (odd counter) বাড়াব, জোড় হলে জোড় কাউন্টার (even counter) বাড়াব। যদি বিজোড় সংখ্যা পাওয়া যায়, তবে জোড় ও বিজোড় কাউন্টার সওয়াপ (swap) করব কারণ বিজোড় সংখ্যা যোগ করলে সাবঅ্যারের প্যারিটি (parity) পরিবর্তন হয়। অবশেষে রেজাল্টে (result) বিজোড় কাউন্ট যোগ করব। এই কোডের কমপ্লেক্সিটি O(n)।
#include <bits/stdc++.h> using namespace std; int main(){ int odd = 0, even = 0, result = 0, n=5, i, temp; int arr[n-1] = { 9,8,7,6,5 }; // অ্যারে ইনিশিয়ালাইজ // প্রতিটি এলিমেন্ট প্রসেস করার লুপ for (i = 0; i < n; i++) { if (arr[i] % 2 == 0) { even++; } else { // জোড়-বিজোড় ভ্যালু সওয়াপ temp = even; even = odd; odd = temp + 1; } result += odd; } cout << "Number of subarrays with odd sum : " << result; }
Number of subarrays with odd sum : 9
এই কোডে, প্রতিটি এলিমেন্ট জোড়/বিজোড় চেক করে জোড় হলে even কাউন্টার বাড়ানো হয়েছে, বিজোড় হলে odd কাউন্টার বাড়ানো হয়েছে। বিজোড় সংখ্যা পাওয়া গেলে odd-even কাউন্টার সওয়াপ করা হয়েছে; না হলে সাবঅ্যারের প্যারিটি পরিবর্তন হয়ত। প্রতিটি ইটারেশনের পর odd কাউন্টারের মান result ভেরিয়েবলে যোগ করা হয়েছে।
এই আর্টিকেলে আমরা বিজোড় যোগফল والے সাবঅ্যারের সংখ্যা বের করার দুটি পদ্ধতি ব্যাখ্যা করেছি: ব্রুট ফোর্স (O(n²)) এবং দক্ষ পদ্ধতি (O(n))। দক্ষ পদ্ধতিতে প্রতিটি এলিমেন্ট প্রসেস করে odd/even কাউন্টার মেইনটেইন করা হয়েছে এবং বিজোড় পাওয়া গেলে কাউন্টার সওয়াপ করা হয়েছে। আশা করি এই আর্টিকেলটি সমস্যা ও সমাধান বোঝাতে সহায়ক হবে।
