इस समस्या में, हमें आकार N का arr[] दिया जाता है जिसमें 1 से N-1 तक के मान होते हैं, जिसमें एक मान सरणी में दो बार होता है। हमारा काम है आकार n के क्रमबद्ध सरणी में एकमात्र दोहराए जाने वाले तत्व को ढूंढना ।
समस्या को समझने के लिए एक उदाहरण लेते हैं,
इनपुट
arr[] = {1, 2, 3, 4, 5, 5, 6, 7} आउटपुट
5
समाधान दृष्टिकोण
समस्या को हल करने का एक सरल तरीका रैखिक खोज का उपयोग करना और यह जांचना है कि क्या गिरफ्तारी [i] और गिरफ्तारी [i + 1] का मान समान है। इस मामले में, वापसी गिरफ्तारी [i] जो मूल्य दोहराया गया है।
उदाहरण 1
हमारे समाधान की कार्यप्रणाली को दर्शाने के लिए कार्यक्रम
#include <iostream>
using namespace std;
int findRepeatingValueArr(int arr[], int N){
for(int i = 0; i < N; i++){
if(arr[i] == arr[i+1])
return (arr[i]);
}
return -1;
}
int main(){
int arr[] = {1, 2, 3, 4, 4, 5, 6};
int N = sizeof(arr)/sizeof(arr[0]);
cout<<"The repeating value in the array is "<<findRepeatingValueArr(arr, N);
return 0;
} आउटपुट
The repeating value in the array is 4
समस्या को हल करने के लिए एक अन्य दृष्टिकोण एक द्विआधारी खोज एल्गोरिथ्म का उपयोग करके उस तत्व को खोजने के लिए है जो मध्य सूचकांक में दो बार हुआ था। यदि मध्य सूचकांक मान खुद को दोहराता है तो उसे प्रिंट करें। अगर यह इंडेक्स पोजीशन पर नहीं है, तो राइट सबअरे को ट्रैवर्स करें अन्यथा लेफ्ट सबएरे को ट्रैवर्स करें।
उदाहरण 2
हमारे समाधान की कार्यप्रणाली को दर्शाने के लिए कार्यक्रम
#include <bits/stdc++.h>
using namespace std;
int findRepeatingValueArr(int arr[], int s, int e){
if (s > e)
return -1;
int mid = (s + e) / 2;
if (arr[mid] != mid + 1){
if (mid > 0 && arr[mid]==arr[mid-1])
return arr[mid];
return arr[findRepeatingValueArr(arr, s, mid-1)];
}
return arr[findRepeatingValueArr(arr, mid+1, e)];
}
int main(){
int arr[] = {1, 2, 3, 4, 5, 6, 6, 7, 8, 9};
int n = sizeof(arr) / sizeof(arr[0]);
cout<<"The repeating value in the array is "<<findRepeatingValueArr(arr, 0, n-1);;
return 0;
} आउटपुट
The repeating value in the array is 6