Given anon-emptyarray of integers, every element appearsthreetimes 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.

Feel free to leave a comment here!!