सी ++ में एक क्रमबद्ध सरणी में मौजूद एक अतिरिक्त तत्व की अनुक्रमणिका खोजें

इस समस्या में, हमें n और n+1 आकार के दो क्रमबद्ध सरणियाँ arr1 और arr2 दिए गए हैं, जिनमें अतिरिक्त तत्व को छोड़कर सभी तत्व समान हैं। हमारा काम एक क्रमबद्ध सरणी में मौजूद एक अतिरिक्त तत्व की अनुक्रमणिका ढूंढना . है ।

समस्या का विवरण: हमें n+1 आकार सरणी से एक तत्व की अनुक्रमणिका खोजने की आवश्यकता है जो आकार n की सरणी में मौजूद नहीं है।

समस्या को समझने के लिए एक उदाहरण लेते हैं,

इनपुट: arr1[n] ={3, 5, 7, 8, 9, 12}
arr2[n+1] ={3, 4, 5, 7, 8, 9, 12}

आउटपुट: 1

स्पष्टीकरण:

मान 4 वाला तत्व अतिरिक्त है जो अनुक्रमणिका 1 पर है।

समाधान दृष्टिकोण -

समस्या का एक सरल समाधान इस तथ्य का उपयोग कर रहा है कि दोनों सरणियों को क्रमबद्ध किया गया है। और केवल एक तत्व के साथ जो बराबर नहीं है, हम रैखिक खोज कर सकते हैं और arr2 में तत्व ढूंढ सकते हैं जो arr1[] में मौजूद नहीं है।

एल्गोरिदम:

चरण 1: i -> 0 से n+1,

चरण 1.1: विषम तत्वों का पता लगाएं, अगर arr1[i] !=arr2[i], ब्रेक लूप।

चरण 2: i का मान लौटाएं।

हमारे समाधान की कार्यप्रणाली को दर्शाने वाला कार्यक्रम,

उदाहरण

#include <iostream>
using namespace std;

int findExtraElement(int arr1[], int arr2[], int n) {
   
   int i;
   for (i = 0; i < n; i++)
      if (arr1[i] != arr2[i])
         break;
   return i;
}

int main()
{
   int arr1[] = {3, 5, 7, 8, 9, 12};
   int arr2[] = {3, 4, 5, 7, 8, 9, 12};
   int n = sizeof(arr1) / sizeof(arr1[0]);
   int extraIndex = findExtraElement(arr1, arr2, n);
   cout<<"The extra element is at index ("<<extraIndex<<") and the value is "<<arr2[extraIndex];
   return 0;
}

आउटपुट

The extra element is at index (1) and the value is 4

अधिक प्रभावी खोज तकनीक का उपयोग करके इस समाधान को बेहतर बनाया जा सकता है जो कि द्विआधारी खोज . है एल्गोरिथम के गणना समय को रैखिक रूप से कम करने के बजाय:

हमारे समाधान की कार्यप्रणाली को दर्शाने वाला कार्यक्रम,

उदाहरण

#include <iostream>
using namespace std;

int findExtraElement(int arr1[], int arr2[], int n) {
   
   int extraIndex = n;
   int start = 0, end = n - 1;
   while (start <= end)
   {
      int mid = (start + end) / 2;
      if (arr2[mid] == arr1[mid])
         start = mid + 1;
      else
      {
         extraIndex = mid;
         end = mid - 1;
      }
   }
   return extraIndex;
}

int main()
{
   int arr1[] = {3, 5, 7, 8, 9, 12};
   int arr2[] = {3, 4, 5, 7, 8, 9, 12};
   int n = sizeof(arr1) / sizeof(arr1[0]);
   int extraIndex = findExtraElement(arr1, arr2, n);
   cout<<"The extra element is at index ("<<extraIndex<<") and the value is "<<arr2[extraIndex];
   return 0;
}

आउटपुट

The extra element is at index (1) and the value is 4

एक और तरीका:

समस्या को हल करने का एक और तरीका दो सरणियों के बीच पूर्ण अंतर को खोजना है, जो कि अतिरिक्त तत्व है। फिर हमें आकार n+1 की सरणी में इस अतिरिक्त तत्व की अनुक्रमणिका खोजने की आवश्यकता है। यह एक खोज एल्गोरिथम का उपयोग करके किया जा सकता है।

हमारे समाधान की कार्यप्रणाली को दर्शाने वाला कार्यक्रम,

उदाहरण

#include <iostream>
using namespace std;

int calcArraysum(int arr[], int n){
   int sum = 0;
   for(int i = 0; i < n; i++)
      sum += arr[i];
   return sum;
}

int findExtraElement(int arr1[], int arr2[], int n) {
   
   int extraValue = calcArraysum(arr2, n+1) - calcArraysum(arr1, n);

   for (int i = 0; i < n; i++)
   {
      if (arr2[i] == extraValue)
         return i;
   }
   return -1;
}

int main()
{
   int arr1[] = {3, 5, 7, 8, 9, 12};
   int arr2[] = {3, 4, 5, 7, 8, 9, 12};
   int n = sizeof(arr1) / sizeof(arr1[0]);
   int extraIndex = findExtraElement(arr1, arr2, n);
   cout<<"The extra element is at index ("<<extraIndex<<") and the value is "<<arr2[extraIndex];
   return 0;
}

आउटपुट

The extra element is at index (1) and the value is 4