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.
Iterate through all elements in
nums
and set up key/value pair.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