XOR use cases

xor-use-cases.ts

// https://florian.github.io/xor-trick/

function swap(a: number, b: number): [number, number] {
  a ^= b;
  b ^= a;
  a ^= b;
  return [a, b];
}

/**
 * @param {number[]} arr :: an array of numbers which contains number 1 ~ `n`, but lacks one of them.
 * @param {number} n     :: the supposed max number of `arr`
 * @returns {number} the lacked number
 * @example findUnknownNumber([1, 2, 3, 5], 5) //=> 4
 * @note This function is also used to find _duplicated_ number of an array.
 *   const findDuplicatedNumber = findUnknownNumber;
 *   findDuplicatedNumber([1, 2, 2, 3, 4, 5], 5) //=> 2
 */
function findUnknownNumber(arr: number[], n: number): number {
  let result = 0;

  for (let i = 1; i < n + 1; i++) {
    result ^= i;
  }

  for (const value of arr) {
    result ^= value;
  }

  return result;
}