Cup of Java #1 - Odd One Out

Welcome to my Cup of Java series, where I'd like to tackle some fun coding challenges/questions and also dive into interesting Java related material.

"White board" questions are quite common in technical interviews. As one can imagine, the pressure to perform while under the spotlight can be overwhelming. Back in 2012, I was asked my first white board question during a technical interview. 

The question went as follows:

"Given an array of integers N, write a method that will return the integer that is repeated an odd number of times. E.g: In the array [1, 1, 6, 2, 1, 6, 2, 1, 2], the odd integer is 2. Note that there will be only one of these integers. The order of the numbers are random."

My first attempt to solve the solution used multiple temporary arrays. The solution worked, but was inefficient, possibly O(n squared). My interviewers asked that if I was given more time, how would I improve on my answer.

The below was second attempt which was definitely a considerable improvement to my previous solution.

public int getOddOneOut(int[] arr)
{
 Hashtable hash = new Hashtable();

 for (int i : arr)
 {
  if (hash.containsKey(i))
   hash.remove(i);
  else
   hash.put(i, i);
 }
 return hash.values().toArray()[0];
}

Bonus Question: What's the Big O notation for the above code?

I hope you found that as an interesting challenge. Till the next cuppa :)