137 Single Number II

Given an array of integers, every element appearsthreetimes except for one, which appears exactly once. Find that single one.

Note: Your algorithm should have a linear runtime complexity. Could you implement it without using extra memory?

Complexity: O(n) time and space

The Idea: Same as just finding a unique number. The problem is trivial (implemented below) if you don't take into account the fact that every number is referenced 3 times. The constant space solution likely involves some bitwise operation on all the elements.

class Solution:
    def singleNumber(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """

        hash_count = {}

        for key in nums:
            if key in hash_count:
                hash_count[key] += 1
            else:
                hash_count[key] = 1

        for key, val in hash_count.items():
            if val == 1:
                return key


obj = Solution()
print(obj.singleNumber([1]))