LeetCode #137 Single Number II

Medium

Problem

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

Example 2:

Input: [0,1,0,1,0,1,99]
Output: 99

Solution

Because there are all odd occurrence of all numbers, it can’t simply use XOR operator to extract the only one. Does that means we can’t use bit operation for this problem? The answer is YES. We can design the digital logic what we need so the only one can still be extracted.

Because every number will appear three times except only one, we need two bits to save the 3 states of all elements. Our goal is to design a logic operation that will be transformed by following this rule: 00 -> 01 -> 10 -> 00. Let’s assume the input is i , the low bit be l, the high bit be h, the new low bit be l’ and the new high bit be h’. We can draw the truth table of the 3 states as follow:

h | l | i | h'| l'
-------------------
0 | 0 | 0 | 0 | 0    => no input, no change
-------------------  
0 | 1 | 0 | 0 | 1    => no input, no change
-------------------
1 | 0 | 0 | 1 | 0    => no input, no change
-------------------
0 | 0 | 1 | 0 | 1    => 00 -> 01
-------------------
0 | 1 | 1 | 1 | 0    => 01 -> 10
-------------------
1 | 0 | 1 | 0 | 0    => 10 -> 00

By above truth table, we can compute h' and l' by h , l and i:

h' = h & ~l & ~i | ~h & l & i with third and fifth rows of truth table

l' = ~h & l & ~i | ~h & ~l & i with second and forth rows of truth table

And the later can further be reduced to:

l' = ~h & (l ^ i) — formula 1.

Moreover, if we let l' be assigned first, h' can also be computed by l':

h' = h & ~i & ~l' | ~h & i & ~l' with third and fifth rows of truth table

which is also equal to

h' = ~l' & (h ^ i) — formula 2.

By formula 1 and 2, we can easily extract the only single one by taking low bit, which means the number whose state still remains 01.

Complexity

It’s trivial that it’s time complexity is O(n) if n denotes to the counts of numbers in the given list. And space complexity is O(1).