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

Brute-force Approach

Iterate through the array and for each element, check if it exists in the rest of the array using linear search. If it does not, return the element.

Time: O(n^2)

Space: O(1)

Better Approach 1

Sort the array and iterate through it, checking if the current element is equal to the next element. If it is not, return the element.

Time: O(nlogn)

Space: O(1)

Better Approach 2

Use an array with length equal to the max element as a hashmap to store the frequency of each element. Iterate through the array and return the element with frequency 1.

Time: O(n)

Space: O(maxElement)

Better Approach 3

Use a set to store the elements. Iterate through the array and add the element to the set if it does not exist. If it does exist, remove it. The single number will be the only element left in the set.

Time: O(n)

Space: O(n)

Better Approach 4

Use a map to store the frequency of each element. Iterate through the array updating the frequencies and return the element with frequency 1.

Time: O(n) for unordered_map, O(nlogn) for map

Space: O(n)

Optimal Approach

Since XOR of a number with 0 is the number itself and XOR of a number with itself is 0, XOR the entire array to find the single number.

Time: O(n)

Space: O(1)