আপনি যদি কখনও C++ ব্যবহার করে থাকেন তবে আপনাকে অবশ্যই জানতে হবে যে সাবয়ারেগুলি কী এবং সেগুলি কতটা দরকারী। আমরা জানি যে, C++-এ আমরা একাধিক গাণিতিক সমস্যা সহজেই সমাধান করতে পারি। তাই এই প্রবন্ধে, আমরা কিভাবে C++-এ এই সাবঅ্যারেগুলির সাহায্যে M বিজোড় সংখ্যাগুলি খুঁজে পেতে পারি তার সম্পূর্ণ তথ্য ব্যাখ্যা করব।
এই সমস্যায়, আমাদের প্রদত্ত অ্যারে এবং পূর্ণসংখ্যা m দিয়ে গঠিত অনেকগুলি সাবয়ারে খুঁজে বের করতে হবে যেখানে প্রতিটি সাবঅ্যারেতে ঠিক m বিজোড় সংখ্যা রয়েছে। তাই এখানে এই পদ্ধতির সহজ উদাহরণ -
Input : array = { 6,3,5,8,9 }, m = 2
Output : 5
Explanation : Subarrays with exactly 2 odd numbers are
{ 3,5 }, { 6,3,5 }, { 3,5,8 }, { 5,8,9 }, { 6,3,5,8 }, { 3,5,8,9 }
Input : array = { 1,6,3,2,5,4 }, m = 2
Output : 6
Explanation : Subarrays with exactly 2 odd numbers are
{ 1,6,3 }, { 3,2,5 }, { 1,6,3,2 }, { 6,3,2,5 }, { 3,2,5,4 }, { 6,3,2,5,4 } প্রথম পদ্ধতি
এই পদ্ধতিতে, একটি প্রদত্ত অ্যারে থেকে সমস্ত সম্ভাব্য সাব্যারে তৈরি করা হয়, এবং প্রতিটি সাবঅ্যারে ঠিক m বিজোড় সংখ্যার জন্য পরীক্ষা করা হয়। এটি একটি সহজ জেনারেট এবং ফাইন্ড পন্থা, এবং এই পদ্ধতির সময় জটিলতা হল O(n 2 )।
উদাহরণ
#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 is size of array, m numbers to be find in subarrays,
// count is number of subarray with m odd numbers
for (int i = 0; i < n; i++){ // outer loop to process each element.
int odd = 0;
for (int j = i; j < n; j++) {// inner loop to find subarray with m number
if (a[j] % 2)
odd++;
if (odd == m) // if odd numbers become equals to m.
count++;
}
}
cout << "Number of subarrays with n numbers are: " << count;
return 0;
} আউটপুট
Number of subarrays with n numbers are: 6
উপরের কোডের ব্যাখ্যা
এই কোডে, আমরা m বিজোড় সংখ্যা সহ সাবয়ারে খুঁজতে নেস্টেড লুপ ব্যবহার করছি, এবং বাইরের লুপ "i" বাড়াতে ব্যবহার করা হয়, যা একটি অ্যারের প্রতিটি উপাদান প্রক্রিয়া করতে ব্যবহার করা হবে৷
অভ্যন্তরীণ লুপটি সাবারে খুঁজে বের করতে এবং বিজোড় কাউন্টার m এ না পৌঁছানো পর্যন্ত উপাদানগুলিকে প্রক্রিয়া করতে ব্যবহৃত হয়, প্রতিটি সাবঅ্যারে পাওয়া ফলাফলের কাউন্টার গণনা বৃদ্ধি করে এবং অবশেষে গণনা ভেরিয়েবলে সংরক্ষিত ফলাফল মুদ্রণ করে৷
দ্বিতীয় পদ্ধতি
আরেকটি পদ্ধতি হল "i" বিজোড় সংখ্যার সাথে উপসর্গের সংখ্যা সংরক্ষণ করার জন্য একটি অ্যারে তৈরি করা, প্রতিটি উপাদান প্রক্রিয়া করা এবং পাওয়া প্রতিটি বিজোড় সংখ্যার জন্য বিজোড় সংখ্যার সংখ্যা বৃদ্ধি করা।
যখন বিজোড় সংখ্যার গণনা m অতিক্রম করে বা সমান হয়ে যায়, তখন উপসর্গ অ্যারেতে (বিজোড় - m ) অবস্থানে সংখ্যাটি যোগ করুন।
যখন বিজোড় m-এর থেকে বড় বা সমান হয়ে যায়, তখন আমরা সূচকটি পর্যন্ত গঠিত সাবয়ারের সংখ্যা গণনা করি এবং গণনা চলকের সাথে "বিজোড় - 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 };
// outer loop to process every element of array
for (i = 0; i < n; i++){
prefix_array[odd] = prefix_array[odd] + 1; // implementing value at odd index in prefix_array[ ]
// if array element is odd then increment odd variable
if (array[i] % 2 == 0)
odd++;
// if Number of odd element becomes equal or greater than m
// then find the number of possible subarrays that can be formed till the index.
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, সম্ভাব্য সাববারের গণনা রাখতে 0 দিয়ে গণনা করছি, 0 এর সাথে বিজোড় এবং 0 এর সাথে 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];
} এই লুপে, আমরা প্রিফিক্স_অ্যারে[ ]-এ বিজোড় সূচকে মান প্রয়োগ করছি, তারপর বিজোড় সংখ্যা পাওয়া গেলে বিজোড় ভেরিয়েবল বৃদ্ধি করছি। আমরা দেখতে পাই যে একটি বিজোড় ভেরিয়েবল m-এর সমান বা তার বেশি হলে সূচক পর্যন্ত সাব্যারে সংখ্যা তৈরি হতে পারে।
অবশেষে, আমরা গণনা ভেরিয়েবলে সংরক্ষিত m বিজোড় সংখ্যা সহ বেশ কয়েকটি সাবয়ারে প্রিন্ট করি এবং আউটপুট পাই।
উপসংহার
এই নিবন্ধে, আমরা দুটি পন্থা থেকে m বিজোড় সংখ্যা সহ সাবয়ারের সংখ্যা খুঁজে বের করার পদ্ধতিটি বুঝতে পারি −
-
প্রতিটি সাবয়ারে তৈরি করা এবং এতে m বিজোড় সংখ্যা পরীক্ষা করা এবং পাওয়া প্রতিটি সাবয়ারের জন্য গণনা বৃদ্ধি করা। এই কোডের সময় জটিলতা হল O(n2)।
-
দক্ষ পদ্ধতি, যা অ্যারের প্রতিটি উপাদানের মধ্য দিয়ে যাচ্ছে এবং একটি প্রিফিক্স অ্যারে তৈরি করছে এবং একটি প্রিফিক্স অ্যারের সাহায্যে ফলাফল খুঁজে বের করছে। এই কোডের সময় জটিলতা হল O(n).
আশা করি আপনি এই নিবন্ধটি সমস্যা এবং সমাধান বুঝতে সহায়ক বলে মনে করেন।
