Given that array is sorted, is a direct hint to go for Binary Search. However, one needs to be careful with implementation, STL isn't going to help here ( :
Solution
Lets say, we are given an array A.
First of all note, size of array has to be odd, as per conditions given in problem.
For sake of understanding, lets remove the integer with frequency as 1 from the array.
Now clearly, since array is sorted and every integer occurs twice, we observe following invariant
Property(Invariant)
All integers at even indices are same as the next number.
Or equivalently, all numbers at odd indices are same as previous number.
Now lets put back the 1-frequency number back into array at its right index, say
j.
Now clearly, above Property holds till j-1.
And, Property doesn't holds after j-1.
In other words, we can binary search on index, say
i and check if Property holds at i, if it does then
i < j, if it doesn't then
j > i.
We recursively apply this to find out index j in
O(log N) and constant space.
C++ Code
int solve(vector A) {
int lo = 0, hi = A.size()-1;
while (lo < hi) {
int mid = (lo + hi) / 2;
if (A[mid] == A[mid^1]) lo = mid + 1; else hi = mid;
}
return A[lo];
}
Note : Here, property is being checked at condition "if (A[mid] == A[mid^1])".
Its a good excercise to think how? (Explained in 1
st comment)
So, if mid is even, then mid^1 = mid + 1.
if mid is odd, then mid^1 = mid - 1.
Now review, property or invariant as explained in above answer, this part of code will become obvious. If not, let me know.