এখানে আমরা একটা সমস্যা দেখব, ধরুন একটা অ্যারে দেওয়া হল। n উপাদান আছে. আমাদের এমন একটি সূচক খুঁজে বের করতে হবে, যেখানে এর বাম দিকের জোড় সংখ্যার কম্পাঙ্ক এবং ডান পাশের জোড় সংখ্যার কম্পাঙ্ক একই, অথবা এর বাম দিকের বিজোড় সংখ্যার কম্পাঙ্ক ডানদিকের বিজোড় সংখ্যার কম্পাঙ্কের সমান। যদি এমন কোন ফলাফল না থাকে তবে -1 ফেরত দিন।
ধরুন অ্যারেটি {4, 3, 2, 1, 2, 4} এর মতো। আউটপুট হল 2। সূচী 2-এর উপাদান হল 2, এটির বামে শুধুমাত্র একটি বিজোড় সংখ্যা রয়েছে এবং এর ডানদিকে একটি মাত্র বিজোড় সংখ্যা রয়েছে।
এই সমস্যা সমাধানের জন্য, আমরা বাম এবং ডান তথ্য সংরক্ষণ করার জন্য জোড়ার দুটি ভেক্টর তৈরি করব। বাম দিকের ভেক্টর তার বাম পাশের বিজোড় এবং জোড় সংখ্যার ফ্রিকোয়েন্সি সংরক্ষণ করবে এবং ডানের ভেক্টর ডান পাশের জন্য একই কাজ করবে। যদি বাম এবং ডানের জন্য জোড় গণনা বা বাম এবং ডানের জন্য বিজোড় গণনা একই হয়, তাহলে সূচকটি ফেরত দিন।
অ্যালগরিদম
getIndex(arr, n) -
Begin define odd and even, and initialize as 0 define left_vector, right_vector for odd even pairs add (odd, even) into left_vector for i in range 0 to n-1, do if arr[i] is even, then increase even, otherwise increase odd add (odd, even) into left_vector done odd := 0 and even := 0 add (odd, even) into right_vector for i in range n-1 down to 1, do if arr[i] is even, then increase even, otherwise increase odd add (odd, even) into right_vector done reverse the right_vector for each element at index i in left_vector, do if left_vector[i].first = right_vector[i].first, or left_vector[i].odd= right_vector[i].odd, then return i done return -1 End
উদাহরণ
#include <iostream>
#include <vector>
#include <utility>
#include <algorithm>
using namespace std;
int getIndex(int n, int arr[]) {
int odd = 0, even = 0;
vector<pair<int, int >> left_vector, right_vector;
left_vector.push_back(make_pair(odd, even));
for (int i = 0; i < n - 1; i++) { //count and store odd and even frequency for left side
if (arr[i] % 2 == 0)
even++;
else
odd++;
left_vector.push_back(make_pair(odd, even));
}
odd = 0, even = 0;
right_vector.push_back(make_pair(odd, even)); //count and store odd and even frequency for right side
for (int i = n - 1; i > 0; i--) {
if (arr[i] % 2 == 0)
even++;
else
odd++;
right_vector.push_back(make_pair(odd, even));
}
reverse(right_vector.begin(), right_vector.end());
for (int i = 0; i < left_vector.size(); i++) {
if (left_vector[i].first == right_vector[i].first ||
left_vector[i].second == right_vector[i].second)
return i;
}
return -1;
}
int main() {
int arr[] = {4, 3, 2, 1, 2};
int n = sizeof(arr) / sizeof(arr[0]);
int index = getIndex(n, arr);
if(index == -1) {
cout << "-1";
} else {
cout << "index : " << index;
}
} আউটপুট
index : 2
