Single Number

Question: Given a non-empty array of integers nums, every element appears twice except for one. Find that single one.

Solution

Approach 1: Hash Table

We use hash table to avoid the O(n) 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.

Approach 2: Math

We can use the following equation to solve the problem:

2 ∗ ( a + b + c ) − ( a + a + b + b + c ) = c