## Approach #1 List operation [Time Limit Exceeded]

**Algorithm**

- iterate all elements in
`nums`

- if some number in
`nums`

is new to array, append it - if some number is already in array, remove it

**Python**

```
class Solution(object):
def singleNumber(self, nums):
"""
:type nums: List[int]
:rtype: int
"""
no_duplicate_list = []
for i in nums:
if i not in no_duplicate_list:
no_duplicate_list.append(i)
else:
no_duplicate_list.remove(i)
return no_duplicate_list.pop()
```

**Complexity Analysis**

- Time complexity : $$O(n^2)$$.

- We iterate through
`nums`

, so the time complexity is $$O(n)$$ - We search the whole list to find whether there is duplicate number, so the time complexity is $$O(n)$$
- Because search is in the
`for`

loop, so we have to multiply both time complexities which is $$O(n * n)$$.

- Space complexity : $$O(n)$$.

We need `list`

to contain elements in `nums`

.

## Approach #2 Hash Table [Accepted]

**Algorithm**

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

- iterate through all elements in
`nums`

- try if
`hash_table`

has the key for`pop`

- if not, set up key/value pair
- in the end, there is only one element in
`hash_table`

, so use`popitem`

to get it

**Python**

```
class Solution(object):
def singleNumber(self, nums):
"""
:type nums: List[int]
:rtype: int
"""
hash_table = {}
for i in nums:
try:
hash_table.pop(i)
except:
hash_table[i] = 1
return hash_table.popitem()[0]
```

**Complexity Analysis**

- 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)$$

- Space complexity : $$O(n)$$.

`hash_table`

needs space for the number of elements in `nums`

.

## Approach #3 Math [Accepted]

**Concept**

2 * (a + b + c) - (a + a + b + b + c) = c

**Python**

```
class Solution(object):
def singleNumber(self, nums):
"""
:type nums: List[int]
:rtype: int
"""
return 2 * sum(set(nums)) - sum(nums)
```

**Complexity Analysis**

- Time complexity : $$O(n + n) = O(n)$$.

`sum`

will call `next`

to iterate through `nums`

.

We 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 in `nums`

.

- Space complexity : $$O(n + n) = O(n)$$.

`set`

needs space for the number of elements in `nums`

## Approach #4 Bit Manipulation [Accepted]

**Concept**

- if XOR zero and some bit, it will return that bit
- a ^ 0 = a

- if XOR two same bits, it will return 0
- a ^ a = 0

- a ^ b ^ a = (a ^ a) ^ b = 0 ^ b = b

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

**Python**

```
class Solution(object):
def singleNumber(self, nums):
"""
:type nums: List[int]
:rtype: int
"""
a = 0
for i in nums:
a ^= i
return a
```

**Complexity Analysis**

- Time complexity : $$O(n)$$.

We only iterate through `nums`

, so the time complexity is the number of elements in `nums`

.

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