## Solution

#### Approach 1: List operation

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

Algorithm

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

1. Iterate through all elements in nums and set up key/value pair.
2. Return the element which appeared only once.

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

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

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 : .