Question: You are given an array containing positive integers. All the integers occur even number of times except one. Find this special integer.

Solution: The integer with the odd number of occurrences will have 0 or more pairs and one single number. So, if we could some how get rid of all the pairs then all we'd be left with is the single number. Now, what gets rid of pairs? Hint: think of an operator.

XOR will do the trick. Its gives you O(n) solution with no extra memory.
int GetSpecialOne(int[] array, int length)
{
int specialOne = array[0];

for(int i=1; i < length; i++)
{
specialOne ^= array[i];
}
return specialOne;
}