Определение единственного уникального числа в массиве

Условие

Дан массив целых чисел, который гарантировано не пустой. В этом массиве каждый элемент встречается ровно два раза, за исключением одного числа, которое присутствует единожды. Требуется написать алгоритм, который возвращает именно это единственное число.

Решение

Используйте XOR всех элементов: x XOR x = 0, а x XOR 0 = x. Парные значения уничтожатся, и останется число, встречающееся один раз.

Пример для Dart:

int singleNumber(List<int> values) {
  var result = 0;
  for (final value in values) {
    result ^= value;
  }
  return result;
}

Время O(n), дополнительная память O(1). Алгоритм опирается на гарантию задачи: все остальные числа встречаются ровно дважды. Он не проверяет эту гарантию и не подходит без изменений для другого числа повторов. При компиляции Dart в JavaScript также учитывайте ограничения платформы на побитовые операции с большими целыми.