Finding single number in a list.

This coding exercise is part of "30-day-leetcoding-challenge" campaign.

The link to the challenge is here: https://leetcode.com/explore/challenge/card/30-day-leetcoding-challenge/528/week-1/3283/

The challenge is to find the only element in the list that appears once only, all other elements appears twice. The solution should be in linear time complexity and use no extra memory.

I used Python dictionary to build a hashing table, to quickly access elements with in O(1), that makes it faster to calculate the frequency of the elements.

But constructing the dictionary is O(N) anyway.

To make it faster, we can remove duplicate element (O(1)) as we go through traversing the list. So instead of calculating the frequency, lets remove duplicate elements from the dictionary.

# Python code

freq = dict.fromkeys(nums , 0)
for el in nums :
    if freq[el] == 0 :
       freq[el] = 1 
    else : # freq == 1, 
       del freq[el] 

# only one non-duplicate element should remain in the dictionary
for key in freq.keys() :
   return key  

The code complexity is O(N), but used extra memory (a dictionary of with the length of N/2).

My solution is better than %88 of the submitted solutions in terms of speed but much worst in terms of used memory.

Solution:

Turns out, the solution is to use logic expressions: XOR. Because bit-wise XOR of the same numbers is zero, and we know all numbers appears twice except one number. Thus eventually the only non-duplicate element will remain.

 a = 0
 for i in nums:
    a ^= i
 return a