Solution

Approach #1 List operation [Time Limit Exceeded]

Algorithm

\n
1. Iterate over all the elements in $$\\text{nums}$$ \n
\n
2. If some number in $$\\text{nums}$$ is new to array, append it
\n
3. If some number is already in the array, remove it
\n

Complexity Analysis

\n
• \n

  Time complexity : $$O(n^2)$$ . We iterate through $$\\text{nums}$$ , taking $$O(n)$$ time. We search the whole list to find whether there is duplicate number, taking $$O(n)$$ time. Because search is in the for loop, so we have to multiply both time complexities which is $$O(n^2)$$ .

  \n
\n
• \n

  Space complexity : $$O(n)$$ . We need a list of size $$n$$ to contain elements in $$\\text{nums}$$ .

  \n
\n

Approach #2 Hash Table [Accepted]

Algorithm

We use hash table to avoid the $$O(n)$$ time required for searching the elements.

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

Complexity Analysis

\n
• \n

  Time complexity : $$O(n * 1) = O(n)$$ . Time complexity of for loop is $$O(n)$$ . Time complexity of hash table(dictionary in python) operation pop is $$O(1)$$ .

  \n
\n
• \n

  Space complexity : $$O(n)$$ . The space required by $$hash\\_table$$ is equal to the number of elements in $$\\text{nums}$$ .

  \n
\n

Approach #3 Math [Accepted]

Concept

\n $$2 * (a + b + c) - (a + a + b + b + c) = c$$ \n

Complexity Analysis

\n
• \n

  Time complexity : $$O(n + n) = O(n)$$ . sum will call next to iterate through $$\\text{nums}$$ .\nWe can see it as sum(list(i, for i in nums)) which means the time complexity is $$O(n)$$ because of the number of elements( $$n$$ ) in $$\\text{nums}$$ .

  \n
\n
• \n

  Space complexity : $$O(n + n) = O(n)$$ . set needs space for the elements in nums

  \n
\n

Approach #4 Bit Manipulation [Accepted]

Concept

\n
• If we take XOR of zero and some bit, it will return that bit
  \n
  • \n $$a \\oplus 0 = a$$ \n
  \n
  \n
\n
• If we take XOR of two same bits, it will return 0
  \n
  • \n $$a \\oplus a = 0$$ \n
  \n
  \n
\n
• \n $$a \\oplus b \\oplus a = (a \\oplus a) \\oplus b = 0 \\oplus b = b$$ \n
\n

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

Complexity Analysis

\n
• \n

  Time complexity : $$O(n)$$ . We only iterate through $$\\text{nums}$$ , so the time complexity is the number of elements in $$\\text{nums}$$ .

  \n
\n
• \n

  Space complexity : $$O(1)$$ .

  \n
\n

Analysis written by: @Ambition_Wang