# [Leetcode problems]137. Single Number II

Given a non-empty 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?
Example 1:
Input: [2,2,3,2] Output: 3

Compared to [Leetcode problems]136. Single Number, this problem sets all other number to appear 3 times. To achieve O(n) time complexity and O(1) space complexity, we again need bitwise operators.

#### Logic

Let’s consider these numbers expressed in binary format. For each bit digit, we would count how many numbers have 1 there, and mod it against 3. Since only 1 item appears once, and all others appear three times, then:

• if the single number has 1 on that position, then there should be 3*x+1 1s. After taking mod against 3, the result is 1.
• if the single number has 0 on that position, then there should be 3*x 1s. After taking mod against 3, the result is 0.

#### Implementation

We can definitely maintain an array arr with the size of 32 where arr[i] corresponding to the i^{th}digit for 32-bit signed binary integer. A more elegant approach is applying bitwise operators: XOR ,AND, and NOT.

We can use two integers one and two to represent the number of 1s on each bit digit. Meaning of one and two:

• For each digit of one, 1 means True – it is one 1 and 0 means False – it is not one 1s.
• For each digit of two, 1 means True – it is two 1 and 0 means False – it is not two 1s.

Let’s walk through it together with an example: [3,4,3,7,7,3,7].

After understanding what are one and two, let’s see how to implement it:

It seems un-readable, right? Don’t worry! Let me explain it a little bit.

• one^nums[i] is to count 1s given a new number; & ~two is to deal with the cases when there are already two 1s.
• two^nums[i] is to count 1s given a new number; & ~two is to deal with the cases when there are previously no 1s.