Number with odd number of occurrence - Amazon

Q. Given an array containing positive integers, all the integers occur even number of times except one. Find this integer occurring odd number of times.

Solution: Sort the array and run a linear search with a counter incrementing on each iteration. On encountering a new number see if the counter value is odd or even. If odd the previous number is the result. Other wise reset the counter. repeat until result is achieved.

To sort O(lg(n)) * search for all --> O(n(lg(n)).

Solution 2:
An XOR operation on a number with itself will nullify it. So as all the numbers except one occurs even number of times. Everything will be 0 except for the number itself. So XOR operation in a loop will get you the answer.

The time complexity will be O(n) here.