সাবাররে একটি অ্যারের সংলগ্ন অংশ। উদাহরণস্বরূপ, আমরা একটি অ্যারে [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++ এ বিজোড় যোগফল সহ সাবয়ারের সংখ্যা খুঁজে বের করার জন্য সম্ভাব্য প্রতিটি তথ্য ব্যাখ্যা করব। বিজোড় যোগফলের সাথে সাবয়ারের সংখ্যা বের করার জন্য, আমরা বিভিন্ন পন্থা ব্যবহার করতে পারি, তাই এখানে এটির জন্য একটি সহজ উদাহরণ দেওয়া হল −
Input : array = {9,8,7,6,5}
Output : 9
Explanation :
Sum of subarray -
{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 ব্রুট ফোর্স অ্যাপ্রোচ
এই পদ্ধতির সাহায্যে আমরা সহজভাবে পরীক্ষা করতে পারি যে সমস্ত সাবঅ্যারেতে উপাদানের যোগফল জোড় বা বিজোড়, যদি এটি জোড় হয় তবে আমরা সেই সাবঅ্যারেকে প্রত্যাখ্যান করব এবং যোগফলের সাথে সাবঅ্যারে গণনা করব, এটি একটি কার্যকর পদ্ধতি নয় কারণ এই কোডের জটিলতা হল O (n 2 )।
উদাহরণ
#include <bits/stdc++.h>
using namespace std;
int main(){
int n=5, temp = 0;
int a[n-1] = { 9,8,7,6,5 } ; // declaring our array.
int cnt = 0; // counter variable.
for(int i = 0; i < n; i++){
temp = 0; // refreshing our temp sum.
for(int j = i; j < n; j++){ // this loop will make our subarrays starting from i till 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
উপরের কোডের ব্যাখ্যা
এই কোডে নেস্টেড লুপ ব্যবহার করা হয় যেখানে বাইরের লুপ I-এর মান বাড়াতে ব্যবহার করা হয়, যা শুরু থেকে অ্যারের প্রতিটি মানের দিকে নির্দেশ করে; অভ্যন্তরীণ লুপটি " i " অবস্থান থেকে শুরু করে সাবাররে খুঁজে পেতে ব্যবহৃত হয় বিজোড় যোগফল।
দক্ষ পদ্ধতি
এই পদ্ধতিতে, আমরা অ্যারের 0 তম অবস্থান থেকে প্রতিটি উপাদান প্রক্রিয়া করছি। যদি বর্তমান উপাদানটি বিজোড় হয়, একটি বিজোড় কাউন্টার বাড়ান এবং প্রতিটি জোড় সংখ্যার জন্য একটি জোড় কাউন্টার বাড়ান। যদি আমরা একটি বিজোড় সংখ্যা খুঁজে পাই, তাহলে জোড় এবং বিজোড়ের মানগুলিকে অদলবদল করুন কারণ সাব্যারেতে একটি বিজোড় সংখ্যা যোগ করলে এর সমতা পরিবর্তন হবে এবং অবশেষে ফলাফলে একটি গণনা যোগ হবে। এই কোডের জটিলতা হল 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}; // initialising the array
// for loop for processing every element of array
for ( i = 0 ; i < n ; i ++ ) {
if ( arr[ i ] % 2 == 0 ) {
even++;
} else {
// swapping even odd values
temp = even;
even = odd;
odd = temp + 1;
}
result += odd;
}
cout << "Number of subarrays with odd sum : " << result;
} আউটপুট
Number of subarrays with odd sum : 9
উপরের কোডের ব্যাখ্যা
এই কোডে, আমরা জোড়/বিজোড়ের জন্য প্রতিটি উপাদান পরীক্ষা করি এবং জোড় সংখ্যার জন্য জোড় কাউন্টার এবং বিজোড় সংখ্যার জন্য বিজোড় কাউন্টার বৃদ্ধি করি। এছাড়াও, একটি বিজোড় সংখ্যা পাওয়া গেলে আমরা বিজোড়-জোড় কাউন্টার মান অদলবদল করছি; অন্যথায়, এটি সাবয়ারের সমতা পরিবর্তন করবে। তারপর প্রতি পুনরাবৃত্তির পর ফলাফল ভেরিয়েবলে বিজোড় কাউন্টারের মান যোগ করা।
উপসংহার
এই নিবন্ধে, আমরা ব্যাখ্যা করেছি কিভাবে ব্রুট ফোর্স পদ্ধতি থেকে যোগ বিজোড় সহ সাবয়ারের সংখ্যা খুঁজে বের করা যায়, যা প্রতিটি সাবঅ্যারে যোগফলের সাথে তৈরি করছে এবং গণনা বৃদ্ধি করছে। এই কোডের সময় জটিলতা হল O(n2)। একটি দক্ষ পন্থা অ্যারের প্রতিটি উপাদানের মধ্য দিয়ে যাচ্ছে এবং প্রতিটি বিজোড়/জোড় সংখ্যার সাথে বিজোড়/জোড় কাউন্টার ভেরিয়েবল বৃদ্ধি করছে এবং একটি বিজোড় সংখ্যা পাওয়া গেলে কাউন্টার অদলবদল করছে; এই কোডের সময় জটিলতা হল O(n)। আশা করি আপনি এই নিবন্ধটি সমস্যা এবং সমাধান বুঝতে সহায়ক বলে মনে করেন।
