Given an array of integers, every element appears twice except for one. Find that single one.

Note:
Your algorithm should have a linear runtime complexity. Could you implement it without using extra memory?

Solution


Approach #1 List operation [Time Limit Exceeded]

Algorithm

  1. Iterate over all the elements in
  2. If some number in is new to array, append it
  3. If some number is already in the array, remove it

Complexity Analysis

  • Time complexity : . We iterate through , taking time. We search the whole list to find whether there is duplicate number, taking time. Because search is in the for loop, so we have to multiply both time complexities which is .

  • Space complexity : . We need a list of size to contain elements in .


Approach #2 Hash Table [Accepted]

Algorithm

We use hash table to avoid the time required for searching the elements.

  1. Iterate through all elements in
  2. Try if has the key for pop
  3. If not, set up key/value pair
  4. In the end, there is only one element in , so use popitem to get it

Complexity Analysis

  • Time complexity : . Time complexity of for loop is . Time complexity of hash table(dictionary in python) operation pop is .

  • Space complexity : . The space required by is equal to the number of elements in .


Approach #3 Math [Accepted]

Concept

Complexity Analysis

  • Time complexity : . sum will call next to iterate through . We can see it as sum(list(i, for i in nums)) which means the time complexity is because of the number of elements() in .

  • Space complexity : . set needs space for the elements in nums


Approach #4 Bit Manipulation [Accepted]

Concept

  • If we take XOR of zero and some bit, it will return that bit
  • If we take XOR of two same bits, it will return 0

So we can XOR all bits together to find the unique number.

Complexity Analysis

  • Time complexity : . We only iterate through , so the time complexity is the number of elements in .

  • Space complexity : .


Analysis written by: @Ambition_Wang