How to optimize the algorithm for solving a problem in JavaScript

Task:

All the numbers in the unsorted array are present twice, except for the one you need to find. Numbers are always valid integers from 1 to 2147483647, so there is no need for type checking and errors. An array contains at least one number and can contain millions of numbers. So make sure your solution is optimized for speed.
Example: with input data [ 1, 8, 4, 4, 6, 1, 8 ] there must be an answer 6.

I solved it in two ways:

  1. slow with two cycles:

function findUnique(numbers) {
  for (var i = 0; i < numbers.length; i++) {
    for (var j = 0; j < numbers.length; j++) {
      if (numbers[i] == numbers[j] && i != j) break;
    }
    if (j == numbers.length) return numbers[i];
  }
}

console.log(findUnique([1, 8, 4, 4, 6, 1, 8]));
  1. it is much faster, but it also fails the speed test

function findUnique(numbers) {
  numbers.sort(function(a, b) {
    return a - b;
  });
  for (var i = 0; i < numbers.length; i += 2) {
    if (numbers[i] != numbers[i + 1]) return numbers[i];
  }
}

console.log(findUnique([1, 8, 4, 4, 6, 1, 8]));

How can I solve the problem even faster?

Author: Harry, 2019-07-12
Source

3 answers

Judging by the information received from the Internet, JS has a bitwise exclusive or - ^ operator.

Apply it to all numbers in a row and get the desired number, which is available in a single instance...

I can make mistakes when writing the code, but something like

function findUnique(numbers) {
  var res = 0;
  for (var i = 0; i < numbers.length; i++) {
    res = res ^ numbers[i];
  }
  return res;
}
console.log(findUnique([1, 8, 4, 4, 6, 1, 8]));
 15
Author: Harry, 2019-07-12 11:09:01

You can optimize @Harry's JavaScript solution in a single line:

function findUnique(numbers) {
  return numbers.reduce((a, b) => a ^ b);
}

console.log(findUnique([ 1, 8, 4, 4, 6, 1, 8 ]));
 2
Author: Valeriy Petukhov, 2019-07-12 11:53:09

I decided to run a small test for clarity and out of curiosity. This answer is not an answer, but to post in the comments, in my opinion, is wild... Regarding the filling of the array, do not kick much, in js it is weak.

So:

// Формируем массив
let arr = new Array;
for(let i = 1; i < 25000; i++){
    arr.push(i + 1);
    arr.push(i);
    arr.push(i - 1);
}

// Добиваем до 75К
arr.push(0);
arr.push(25000);

// Добавляем уникальное значение
arr.push(25001);

// Рандомизируем
arr.sort();

// Тестируем
const start = new Date().getTime();
console.log(findUnique(arr));
const end = new Date().getTime();
console.log(end - start + 'ms');

Totals (here A is the slow TS function, B is the fast TS function, C is the response from @Harry) 

A: 646ms - 834ms (ответ 25001 - правильный)
B: 7ms - 11ms (ответ 2)
C: 1ms - 2ms (ответ 15)

Either I'm a fool, or the skis don't go...

 0
Author: DaemonHK, 2019-07-12 12:02:36