Solving the Single Number problem in Python

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
Tags:
0 0 vote
Article Rating
Subscribe
Notify of
guest
0 Comments
Inline Feedbacks
View all comments