Search code examples
javascriptxor

I don't understand what is happening with this XOR

I am working on this problem. "Given an array, find the int that appears an odd number of times. There will always be only one integer that appears an odd number of times." I came up with this solution online:

function findOdd(A) {
var n = 0;
  for(var i = 0; i < A.length; i++){
  n = n^A[i];
  }

  return n;
}

This works but I am not sure why and i was hoping someone could explain it to me. I just don't understand the line:

n = n^A[i];

Could you please tell me what it is doing in this instance?

Solution

  • Xoring any number with itself will result in 0. If you know that there's only one number that appears an odd number of times, the others will cancel themselves out by self-xoring, and the answer will be the remaining number that appears an odd number of times.