सी ++ में दोनों तरफ सम या विषम संख्याओं की समान गणना के साथ ऐरे इंडेक्स

यहां हम एक समस्या देखेंगे, मान लीजिए कि एक सरणी दी गई है। एन तत्व हैं। हमें एक सूचकांक ज्ञात करना है, जहाँ इसके बायीं ओर की सम संख्याओं की बारंबारता और इसके दायीं ओर की सम संख्याओं की बारंबारता समान हो, या इसके बायीं ओर की विषम संख्याओं की आवृत्ति इसके दाईं ओर की विषम संख्याओं की आवृत्ति के समान हो। यदि ऐसा कोई परिणाम नहीं है, तो -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