Skip to content

Instantly share code, notes, and snippets.

@unilecs
Last active October 10, 2017 07:25
Show Gist options
  • Save unilecs/d312f1714d94b0010121aa791a4108e4 to your computer and use it in GitHub Desktop.
Save unilecs/d312f1714d94b0010121aa791a4108e4 to your computer and use it in GitHub Desktop.
Get number w/o pair in the array of numbers (two unique numbers)
function getUniqueNumbersInArray(arr) {
let first = 0, second = 0;
// xor by each element
let xor = arr[0];
for (let i = 1; i < arr.length; i++) {
xor ^= arr[i];
}
// берем крайний правый ненулевой бит
// в нашем примере, xor = 14 (1110); 13 (1101)
let rightBit = xor & ~(xor-1); // 2 (0010)
// Находим xor для всех элементов у которых этот бит установлен в 1
for (let i = 0; i < arr.length; i++) {
if ((arr[i] & rightBit) > 0) {
first ^= arr[i];
}
}
// second = first ^ (first^second)
second = first ^ xor;
console.info(first);
console.info(second);
}
const arr = [ 0, 4, -1, 7, -1, 4, 9, 0];
getUniqueNumbersInArray(arr);
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment