এখানে আমরা একটি সমস্যা দেখব, মনে করুন একটি অ্যারে দেওয়া আছে। n এলিমেন্ট আছে। আমাদের একটি ইনডেক্স খুঁজে বের করতে হবে, যেখানে এর বাম পাশের জোড় সংখ্যাগুলোর ফ্রিকোয়েন্সি এবং ডান পাশের জোড় সংখ্যাগুলোর ফ্রিকোয়েন্সি সমান, অথবা এর বাম পাশের বিজোড় সংখ্যাগুলোর ফ্রিকোয়েন্সি এবং ডান পাশের বিজোড় সংখ্যাগুলোর ফ্রিকোয়েন্সি সমান। যদি এমন কোনো ফলাফল না থাকে, তবে -1 রিটার্ন করুন।
মনে করুন অ্যারেটি এরকম {4, 3, 2, 1, 2, 4}। আউটপুট ২। ইনডেক্স ২-এ এলিমেন্ট ২, এর বাম পাশে শুধু একটি বিজোড় সংখ্যা আছে, এবং ডান পাশেও শুধু একটি বিজোড় সংখ্যা আছে।
এই সমস্যাটি সমাধান করার জন্য, আমরা দুটি ভেক্টর অফ পেয়ার তৈরি করব লেফট এবং রাইট ইনফরমেশন সংরক্ষণ করতে। লেফটের জন্য ভেক্টরটি এর বাম পাশের বিজোড় এবং জোড় সংখ্যার ফ্রিকোয়েন্সি সংরক্ষণ করবে, এবং রাইটের জন্য ভেক্টরটি ডান পাশের জন্য একই কাজ করবে। যদি লেফট এবং রাইটের জোড় কাউন্ট বা বিজোড় কাউন্ট সমান হয়, তবে ইনডেক্সটি রিটার্ন করুন।
অ্যালগরিদম
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
