# XOR, one pass

• The idea is based on:
`(1 ^ 2 ^ 3 ^ .. ^ n) ^ (1 ^ 2 ^ 3 ^ .. ^ n) = 0`
Suppose we change 'a' to 'b', then all but 'a' and 'b' are XORed exactly 2 times. The result is then
`0 ^ a ^ b ^ b ^ b = a ^ b`
Let `c = a ^ b`, if we can find 'b' which appears 2 times in the original array, 'a' can be easily calculated by `a = c ^ b`.

``````    public int[] findErrorNums(int[] nums) {
int n = nums.length;
int[] count = new int[n];
int[] ans = {0,0};
for(int i = 0; i < n; i++) {
ans[1] ^= (i+1) ^ nums[i];
if (++count[nums[i]-1] == 2)
ans[0] = nums[i];
}
ans[1] ^= ans[0];
return ans;
}
``````

O(0) space:

``````    public int[] findErrorNums(int[] nums) {
int[] ans = new int[2];
for(int i = 0; i < nums.length; i++) {
int val = Math.abs(nums[i]);
ans[1] ^= (i+1) ^ val;
if (nums[val-1] < 0) ans[0] = val;
else nums[val-1] = -nums[val-1];
}
ans[1] ^= ans[0];
return ans;
}
``````

• @tyuan73 great solutions

• @tyuan73 said in XOR, one pass:

else nums[val-1] = -nums[val-1];

I think the 'else' here is redundant.

• @tyuan73 good

• can you explain this solution? thanks!

• @tyuan73 said in XOR, one pass:

if (nums[val-1] < 0) ans[0] = val;

If you use this method to find the duplicate, then the missing can be easily founded by sum{1,...n}-sum_of_the_input_array+duplicate, hence there is no need to use xor to get 1-pass O(n)/O(1) solution.

• @rikimberley There are 2 advantages XOR over sum: 1. XOR is slightly faster; 2. sum(1..n) may overflow.

• @tyuan73 sum{1,...n}-sum_of_the_input_array can be implemented in the pass (sumdiff += (i+1)-abs(nums[i])

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