Find single integer using Hashmap

A coding question: Given an array of integers, every element appears twice except for one. Find that single one. It requires a linear runtime complexity.

My solution:

public class Solution {
    public int singleNumber(int[] A) {
    HashMap<Integer, Integer> lut = new HashMap<Integer, Integer>();
     for (int i=0; i<A.length; i++){
         if(lut.containsKey(A[i])){
             lut.remove(A[i]);
         }
         else{
             lut.put(A[i],1);
         }
     }

     Set<Integer> keys = lut.keySet();
     System.out.println(keys.size());
     for(Integer integer: keys)
         return integer;

     return (Integer) null;
 }

}

I think the complexity isO(n), because that it go through the array only once and HashMap using fixed time to get an element. But after judging it online, it says that my codes time limit. Can someone point out why this exceed the time limit? How to improve?

Jon Skeet
people
quotationmark

I suspect the time limit has been set with a specific implementation in mind. Your solution looks like it should be linear time to me - but it's probably a significantly larger constant factor than this code:

public int findSingleNumber(int[] array) {
    int result = 0;
    for (int item : array) {
        result ^= item;
    }
    return result;
}

This uses the fact that all items except the one we want appear exactly twice, so if they're XORed together they'll cancel each other out. We're left with just the number we're looking for.

I would add that puzzles like this are fun and stretch the mind - but the solutions are rarely ones that you'd want to use in real applications.

people

See more on this question at Stackoverflow