Tìm số xuất hiện số lần lẻ trong mảng JavaScript

Mô tả bài toán

Cho mảng số nguyên, đúng 1 số xuất hiện số lần lẻ. Tìm số đó bằng cách sắp xếp rồi đếm.

Ví dụ minh họa

const arr = [20, 1, -1, 2, -2, 3, 3, 5, 5, 1, 2, 4, 20, 4, -1, -2, 5];

const findOdd = arr => {
  let count = 0, last;
  arr.sort((a, b) => a - b);
  for (let i = 0; i < arr.length; i++) {
    if (arr[i] === last) { count++; continue; }
    if (count % 2) return last;
    last = arr[i];
    count = 1;
  }
  return last;
};

console.log(findOdd(arr));

Kết quả

5

Cách tối ưu O(n) time, O(1) space: XOR

const findOdd = arr => arr.reduce((a, b) => a ^ b);

Giải thích XOR

• a ^ a = 0
• a ^ 0 = a
• XOR giao hoán, kết hợp
• Các cặp số chẵn lần triệt tiêu nhau, chỉ còn số lẻ lần