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)