[LeetCode] 137. Single Number II

Problem : https://leetcode.com/problems/single-number-ii/

Hash based solution:

class Solution:
    def singleNumber(self, nums: List[int]) -> int:
        for n, count in Counter(nums).items():
            if count == 1:
                return n

O(1) space complexity solution:

import ctypes

class Solution:
    def singleNumber(self, nums: List[int]) -> int:
        result = 0
        
        # calculate sum of bit on each position
        for shift in range(32):
            sum_of_bit = 0
            
            for n in nums:
                mask = 1 << shift
                
                if n & mask != 0:
                    sum_of_bit += 1
            
            # sum_of_bit = 0, if there is no bit from the unique number
            # on this position
            sum_of_bit = sum_of_bit % 3
            
            result = result | sum_of_bit << shift
        
        # convert to integer 
        return ctypes.c_int(result).value