This website contains ALL LeetCode **Premium** problems for
**FREE!!**.

All leaked interview problems are collected from Internet.

All leaked interview problems are collected from Internet.

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?

b'

\n## Solution

\n

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

\n

\n#### Approach #2 Hash Table [Accepted]

\n

\n#### Approach #3 Math [Accepted]

\n

\n#### Approach #4 Bit Manipulation [Accepted]

\n

\n

'
\n\n

\n\n

**Algorithm**

- \n
- Iterate over all the elements in \n \n
- If some number in is new to array, append it \n
- If some number is already in the array, remove it \n

**Complexity Analysis**

- \n
- \n
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

\n`for`

loop, so we have to multiply both time complexities which is . \n - \n
Space complexity : . We need a list of size to contain elements in .

\n \n

\n

**Algorithm**

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

\n- \n
- Iterate through all elements in \n \n
- Try if has the key for
`pop`

\n - If not, set up key/value pair \n
- In the end, there is only one element in , so use
`popitem`

to get it \n

**Complexity Analysis**

- \n
- \n
Time complexity : . Time complexity of

\n`for`

loop is . Time complexity of hash table(dictionary in python) operation`pop`

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

\n \n

\n

**Concept**

\n\n

\n\n**Complexity Analysis**

- \n
- \n
Time complexity : .

\n`sum`

will call`next`

to iterate through .\nWe can see it as`sum(list(i, for i in nums))`

which means the time complexity is because of the number of elements() in . \n - \n
Space complexity : .

\n`set`

needs space for the elements in`nums`

\n

\n

**Concept**

- \n
- If we take XOR of zero and some bit, it will return that bit
- \n
- \n\n \n

\n - If we take XOR of two same bits, it will return 0
- \n
- \n\n \n

\n - \n\n \n

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

\n\n**Complexity Analysis**

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

\n \n - \n
Space complexity : .

\n \n

\n

Analysis written by: @Ambition_Wang

\n