Given an array consisting of integers in range 1 to n consisting of only one duplicate element. Find out the duplicate element in O(logN) time.
Examples:
Input : 6 1 1 2 3 4 5 Output : 1 Input : 5 1 2 3 4 4 Output : 4
Using Binary Search:
#include <bits/stdc++.h>
using namespace std;
int find_only_repeating_element(int arr[], int n) {
int low = 0;
int high = n - 1;
while (low <= high) {
int mid = low + (high - low) / 2;
if (arr[mid] == arr[mid + 1] || arr[mid] == arr[mid - 1]) {
return arr[mid];
}
if (arr[mid] < mid + 1) {
high = mid - 1;
} else {
low = mid + 1;
}
}
return -1;
}
int main() {
int n;
cin >> n;
int *arr = new int[n];
for (int i = 0; i < n; i++) {
cin >> arr[i];
}
cout << find_only_repeating_element(arr, n) << endl;
delete[] arr; // Deallocate memory
return 0;
}
Time Complexity: O(logN)
