इस समस्या में, हमें दो सॉर्टेड सरणी arr1 और arr2 दी गई हैं जिनका आकार n और n+1 है जिसमें सभी तत्व समान हैं सिवाय अतिरिक्त तत्व के। हमारा कार्य एक सॉर्टेड सरणी में मौजूद अतिरिक्त तत्व का सूचकांक ढूंढना है।
समस्या विवरण: हमें 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
