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).
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