Single Number II

Question

Given an array of integers, every element appears three times 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?

Tags

• Bit Manipulation

Thought

We utilize the algorithm proposed here: https://discuss.leetcode.com/topic/17629/the-simplest-solution-ever-with-clear-explanation/8

Use the mod of 3 to remove the number appeared 3 times in the array.

Code

class Solution(object):
    def singleNumber(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        # Utilize the bit operation
        # https://discuss.leetcode.com/topic/17629/the-simplest-solution-ever-with-clear-explanation/2
        b1, b0 = 0, 0
        for num in nums:
            b0 = (b0 ^ num) & (~b1)
            b1 = (b1 ^ num) & (~b0)
        return b0