# Adaptive bitwise O(n) solution, straightforward state transition

• This solution is inspired by and based on @againest1 's solution at here and @woshidaishu 's explanation in the follow-up. Thank you, guys!

In againest1's solution, many people are wondering how did he come up with the true table. Well, here in my solution, the state transition is pretty straightforward.

``````/**
*Result:
* 11 / 11 test cases passed.
* Status: Accepted
* Runtime: 1 ms
* Your runtime beats 86.59% of javasubmissions.
*Date:
* 9/2/2016
*/
public class Solution {
public int singleNumber(int[] nums) {
int one = -1;
int two = 0;
int three = 0;
for(int e : nums){
int tmpthree = three;
three = (three&~e) | (two & e);
two = (two&~e) | (one & e);
one = (one&~e) | (tmpthree & e);
}
return ~one;
}
}
``````

The basic idea is that we view each bit individually and independently. We count the appearance of each bit by pushing the flag bit (1, initiated by `int one=-1`) circularly from `one` to `two`, then to `three`, and then to `one`, and repeat it. Every bit 1 is "following forward" by one step when the corresponding bit in `e` is 1.

Take the line `three = (three&~e) | (two & e);` for example.

• `e` serves as a mask.
• `(two &e)` is extracting the bits in `two` masked by `e`. It is the bits that we want to push to `three`.
• `(three&~e)` is extracting the bits not masked by `e`. It is the bits that we want to keep remained in `three`.
• `three = (three&~e) | (two & e)` is the result of new `three` after pushing the masked bits of `two` forward to `three`.

Finally, after traversing all numbers, `two` is the single number. `~one==two`.

This solution is still correct in cases like `[1,1,1,2,2,2,3,3]` and `[1,1,1,1,1,1,2]`.
With small changes, this solution is also adaptive to questions like:

• "Every element appears k (k>1) times except for one." (Replace variables `one`, `two`, `three` with an array of length k. Time complexity is O(nk). )
• "Every element appears k (k>2) times except for one appearing k-1 times and one appearing k-2 times. (return non-zero values of `two`, `three`, `four`, etc.)

• actually one, two and three are extra spaces right?

So you are still using extra space of 3 integers

• Sorry you are not correct. The `one` `two` `three` extra space is for local variables in the memory stack. Actually, the program uses much much more memory spaces than 3 integers' space, including heap area, method area, Java VM stack, native method stack, so on and so on, and even registers!

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.