# O(n) time O(1) space Java code

• ## Idea

Suppose `C = A ^ B`, then the `1` bits in `C` are exactly the ones that only exist in either `A` or `B` (`C` cannot be `0` or `A` and `B` would be the same). It is because all other elements appearing twice are turned into `0` during the XOR process. The XOR result `C` is actually the XOR of the only two elements each appearing once.

Thus, for whichever `1` bit in `C`, "having it or not" can be the condition for dividing those elements into `Group A`(which containing `A`) and `Group B` (which containing `B`). As per to the explanation above, the XOR result of those elements in `Group A` (except for `A`) would be `0`, and the XOR of all elements in `Group A` would be `A`. It's the same story in `Group B`.

## Java Code

``````public class Solution {
public int[] singleNumber(int[] nums) {
int c = 0;
for (int num : nums) {
c ^= num;
}
// get the lowest "1" bit of C
c &= -c;
// rets[0], rets[1] would be the XOR results of Group A and Group B
int[] rets = new int[2];
for (int num : nums) {
if ((num & c) == 0) {
rets[0] ^= num;
}
else {
rets[1] ^= num;
}
}
return rets;
}
}
``````

How to get the lowest `1` bit of C
For a positive integer `C`, `-C` would be stored as `2's complement` of `C` and with the highest bit (sign bit) set to `1`. To compute the `2's complement` of an integer, simply keep the trailing `0`s and the lowest `1` bit unchanged, and then revert all the higher bits. So, `C & (-C)` would be the lowest `1` bit of `C`.

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