The challenge
Given a non-empty 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?
Example 1:
Input: [2,2,1] Output: 1
Example 2:
Input: [4,1,2,1,2] Output: 4
The solution in Python
def singleNumber(nums): # create a dictionary/hashmap found = {} # loop through the nums for i in nums: # add to map if not found if i not in found: found[i] = i else: # otherwise remove it del found[i] # loop through the found map and return the first item for i in found: return i