'''
keys: 
Solutions:
Similar: 
T:
S:
'''
from typing import List
from collections import Counter




class Solution:
    # two bitmasks
    '''
    x & (-x) keeps the rightmst 1-bit and sets all the other bits to 0
    https://leetcode.com/problems/single-number-iii/discuss/68900/Accepted-C%2B%2BJava-O(n)-time-O(1)-space-Easy-Solution-with-Detail-Explanations
    '''
    def singleNumber1(self, nums: List[int]) -> List[int]:
        # difference between two numbers (x and y) which were seen only once
        bitmask = 0
        for num in nums:
            bitmask ^= num
        
        # rightmost 1-bit diff between x and y
        diff = bitmask & (-bitmask)
        
        res = [0, 0]
        for num in nums:
            if num & diff == 0: # the bit is not set
                res[0] ^= num
            else: # the bit is set
                res[1] ^= num
        return res
        
    
    # self-made; O(N) for S and T
    def singleNumber(self, nums: List[int]) -> List[int]:
        if not nums: return []
        
        res = []
        for k, v in Counter(nums).items():
            if v == 1:
                res.append(k)
        return res
