सी ++ में एक सरणी में फैक्टोरियल का योग खोजें

विचार करें कि हमारे पास एक सरणी ए है, जिसे क्रमबद्ध किया गया है। इसमें सभी तत्व दो बार प्रकट होते हैं, लेकिन एक तत्व केवल एक समय के लिए मौजूद होता है। हमें उस तत्व को खोजना होगा। यदि सरणी [1, 1, 3, 3, 4, 4, 5, 6, 6, 7, 7, 9, 9] है, तो एकल तत्व 5 है।

हम इसे हल करने के लिए द्विआधारी खोज दृष्टिकोण का उपयोग करेंगे। एकल तत्व से पहले सभी तत्वों की पहली घटना सूचकांक 0, 2, 4, ... और पहली घटना सूचकांक 1, 3, 5, ... पर होती है, लेकिन एकल तत्व के बाद, पहली संख्या की सभी घटनाएं विषम सूचकांक पर होंगी, और दूसरा तत्व सम इंडेक्स पोजीशन पर होगा।

तो पहले मध्य सूचकांक मध्य ज्ञात करें, यदि मध्य सम है, तो ए [मध्य] और ए [मध्य + 1] की तुलना करें, यदि दोनों समान हैं, तो आवश्यकतानुसार बाएं या दाएं जाएं। अन्यथा जब मध्य विषम हो, तो A[मध्य] और A[मध्य -1] की तुलना करें, यदि वे समान हैं, तो आवश्यकतानुसार बाएँ या दाएँ जाएँ।

उदाहरण

#include<iostream>
using namespace std;
void findSingleElement(int *arr, int left, int right) {
   if (left > right)
      return;
   if (left==right) {
      cout << "The required element is: "<< arr[left];
      return;
   }
   int mid = (left + right) / 2;
   if (mid%2 == 0) {
      if (arr[mid] == arr[mid+1])
         findSingleElement(arr, mid+2, right);
      else
         findSingleElement(arr, left, mid);
   }else{
      if (arr[mid] == arr[mid-1])
         findSingleElement(arr, mid+1, right);
      else
         findSingleElement(arr, left, mid-1);
   }
}
int main() {
   int arr[] = {1, 1, 3, 3, 4, 4, 5, 6, 6, 7, 7, 9, 9};
   int len = sizeof(arr)/sizeof(arr[0]);
   findSingleElement(arr, 0, len-1);
}

आउटपुट

The required element is: 5