I think we can do it in $log(N)$ complexity consider the example array$= [1,1,2,2,3,4,4] $and we need to find 3 now i will represent the indexes of the array also $a[0]=1$
$a[1]=1$
$a[2]=2$
$a[3]=2$
$a[4]=3$
$a[5]=4$
$a[6]=4$
As 1st occurrence of an element is represented in even indexes and repeated occurrence of element is at odd index., algorithm will be like this
Thus it will take $O(log n)$ complexity link in geeksforgeeks https://www.geeksforgeeks.org/find-the-element-that-appears-once-in-a-sorted-array/
check out this link https://www.geeksforgeeks.org/find-the-element-that-appears-once-in-a-sorted-array/
but algo is saying go to right for a[3]==a[4] so here we need to search in right half where 1 is not present
see the algo( answered above by Albin Paul )
Actually, it can take n/2 times. rt?
Means assign 1st one and compare with 2nd one
if it matches, then go to assign 3rd one
i.e, check like this
while(i<n) { if(a[i]==a[i+1]) a[i]=a[i+2]; else int found=a[i]; }
This can be solved in time $O(logn)$ using binary search. Since we are given $n$, $n$ must be odd(all pairs except x).
If the element at index $mid =( 0 + n -1)/2$ is $ x$, we are done. Otherwise say its $array[mid] = y$.
For simplicity assume that $mid$ is even and if $array[mid] = array[mid-1] $, then $x$ must be present in the left half of the array. The reason is that the number of elements from $0$ to $mid - 2$ is odd(because of x) and the array is sorted.
If $array[mid] = array[mid+1]$ , then $x$ must be present in the right half for similar reasons.
Now assume that $mid$ is odd and if $array[mid] = array[mid-1] $, then $x$ must be present in the right half of the array. The reason is that the number of elements from $mid+1$ to $n- 1$ is odd(because of x) and the array is sorted.
If $array[mid] = array[mid+1] $ , then $x$ must be present in the left half for similar reasons. Recursively solve the problem using this approach using binary search.
64.3k questions
77.9k answers
244k comments
80.0k users