XOR operator in programming use case

A few days ago, i solved a kata (programming problem) in codewar website, when i finished, i checked the other solutions found. I saw a solution that caught my attention, this solution uses XOR operation. You can easily understand XOR operator logic (truth table) but the purpose is to understand WHY XOR resolves the problem. So i did some research and i will try to explain you my understanding.

Kata problem

So the programming problem was:

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.

So if you have a list like: [2, 3, 2, 4, 4]
3 is the good answer. 2 and 4 are repeated 2 times (even) and 3 just 1 > (odd)

Try to resolve this problem if you want. I did it with JavaScript and a forEach loop.
I will leave you my solution at the end of this post.
The solution given by other users is:

const findOdd = (xs) => xs.reduce((a, b) => a ^ b);
// this is arrow function

They use reduce function to iterate in the 'xs' list and ^ (XOR operator in JavaScript).

Understand

So first of all, you need to understand 3 THINGS:

^ = means XOR operation

1. Truth table

0 ^ 0 = 0
0 ^ 1 = 1
1 ^ 0 = 1
1 ^ 1 = 0

(this is useful to understand Properties below)

2. Properties:

Capital letters as A or B or X are the result of a xor operation.

A ^ A = 0
A ^ 0 = A

[A] can be a random number, for example 10 ^ 10 = 0
or 3 ^ 0 = 3

(ps: we don't need the other properties to understand next parts)

3. Associativity:

a ^ b ^ c = a ^ c ^ b
or even
a ^ b ^ c ^ d = a ^ c ^ d ^ b

So this means that the priority order of operations
can be changed.

This is not mandatory to start with a ^ b operation, we can
start with a ^ c if you we want.

Apply

OK now we will see how to apply XOR in this case.

Take this list as example

const array = [10, 3, 20, 10, 3, 20, 10]

here 10 is the number that is repeated odd times (3). It's the good
answer.
Reduce is a special function to javascript. Basically this function iterates each list element from LEFT to RIGHT and returns the result of a given operation between the previous and current iteration element.

So in our problem/example the list element is a number and the given operation is the XOR operation a ^ b. a will be the previous result and b the number of the current iteration.

This solution will iterate like this:

1. 10 ^ 3 = A (the result is 9 but we don't need to know real
   results, so we call it A)

2. A ^ 20 = B it's the same as 10 ^ 3 ^ 20 so B = 10 ^ 3 ^ 20 ..and so on

3. 10 ^ 3 ^ 20 ^ 10. At this moment we can use associativity,
   to change the order of prio operations.
   So we can write 10 ^ 10 ^ 3 ^ 20, now use the properties (A ^ A = 0)
   so 10 ^ 10 = 0 ... then 0 ^ 3 ^ 20.
   Again use the property (A ^ 0 = A).. so 0 ^ 3 ^ 20 = 3 ^ 20.

4. 3 ^ 20 ^ 3 .. Again use associativity and properties, the result
   here is 20

5. 20 ^ 20 = 0, then last iteration

6. 0 ^ 10 = 10 ! AWESOME !

Conclusion

As you can see, the behaviour is that, if at a time we meet/encounter a number thats was ALREADY IN previous XOR operations .. like : [a] ^ b ^ c ^ [a] the repeated number [a] is somehow canceled or removed. A duplicate number will be removed step by step so at the end the number/result will be the number that has appeared only once (1 = odd)

Thats why XOR operation can resolve this kind of problem.

Thanks for reading 😌 !

Below, i leave you my solution (draft), i know, i don't respect clean code here 🤷‍♂️

function findOdd(A) {
  const occurencesTable = [];

  A.forEach(number => {
    const exist = occurencesTable.find(occurence => {
      return occurence[0] === number;
    });

    if (!exist) {
      occurencesTable.push([number, 1]);
    } else {
      exist[1] = exist[1] + 1;
    }
  });

  const odd = occurencesTable.find(occurence => {
    return (occurence[1] % 2 !== 0)
  });
  return odd[0];
}