singleNumber.py

import itertools, functools, operator
from typing import *
class Solution:
    def singleNumber(self, lst: List[int], k: int) -> int:
        pattern = []
        for i in itertools.count():
            if k & 1 != 0:
                pattern.append(i)
            k >>= 1
            if k == 0:
                break
        if len(lst) == 1:
            return lst[0]
        # first two can cause problem
        lst[1], lst[0] = lst[1]&lst[0], lst[1]^lst[0]
        for i in range(2, len(lst)):
            j = 0
            while lst[i] != 0:  # carry != 0
                # carry, half-sum
                lst[i], lst[j] = lst[i] & lst[j], lst[i] ^ lst[j]
                j += 1
            rm = functools.reduce(operator.and_, (lst[bi] for bi in pattern))
            for bi in pattern:
                lst[bi] &= ~rm
        return lst[0]

test.py

import unittest
from singleNumber import Solution

class TestSolution(unittest.TestCase):
    def __init__(self, methodName='runTest'):
        super().__init__(methodName)
        self.solinst = Solution()

    def test_case1(self):
        self.assertEqual(2, self.solinst.singleNumber([1,2,1,3,3,3,1], 3))

    def test_case2(self):
        self.assertEqual(4, self.solinst.singleNumber([1,2,3,1,2,3,1,2,3,1,2,3,1,2,3,4], 5))

    def test_case3(self):
        import random
        m = random.sample(range(100), 11)
        ans = m[0]
        m = m[:1] + m[1:]*100
        random.shuffle(m)
        self.assertEqual(ans, self.solinst.singleNumber(m, 100))


if __name__ == '__main__':
    unittest.main()