<?php

function findIt(array $seq) : int
{   
    
    if (count($seq) == 1) return $seq[0];
  
    // make glossary: key - number; value - quantity
    $glossary = [];
  
    foreach($seq as $num) {
      if (isset($glossary[$num])) {
        $glossary[$num] +=1; 
      } else {
        $glossary[$num] = 1;
      }
    }
    
    $result = array_keys(array_filter($glossary, function($value) {
    	return $value % 2 !== 0; 
    }));
    
    return $result[0];
}

var_dump(findIt([20,1,-1,2,-2,3,3,5,5,1,2,4,20,4,-1,-2,5]));

// Output
int(5)

I’ve used method “glossary”. I used a frequency map to count how many times each number appears.

array(8) {
  [20]=>
  int(2)
  [1]=>
  int(2)
  [-1]=>
  int(2)
  [2]=>
  int(2)
  [-2]=>
  int(2)
  [3]=>
  int(2)
  [5]=>
  int(3)
  [4]=>
  int(2)
}

But there is function array_count_values.

function findIt(array $seq) : int
{
    $nums = array_count_values($seq);
    foreach ($nums as $key => $val) {
      if ($val % 2) {
        return $key;
      }
    }
}

It returns array:

array(8) {
  [20]=>
  int(2)
  [1]=>
  int(2)
  [-1]=>
  int(2)
  [2]=>
  int(2)
  [-2]=>
  int(2)
  [3]=>
  int(2)
  [5]=>
  int(3)
  [4]=>
  int(2)
}

Or we can use array_reduce:

function findIt(array $seq) : int
{
    return array_reduce($seq, function($carry, $value) {
          return $carry ^ $value;
    });
}

array_reduce последовательно «сворачивает» массив в одно значение.

На каждом шаге:

carry = результат прошлого шага
value = текущий элемент массива

Функция возвращает новый carry.

То есть происходит цепочка:

((a ^ b) ^ c) ^ d ...

В итоге остаётся одно число.

Магия оператора XOR (^)

Вот где начинается настоящая математика.

Свойства XOR:

x ^ x = 0        одинаковые уничтожаются
x ^ 0 = x        ноль ничего не меняет
XOR коммутативен и ассоциативен

Это значит:

• порядок не важен
• пары одинаковых чисел взаимно обнуляются

Пример

[1, 2, 2, 1, 3]

Вот что произойдет:
(1 ^ 1) ^ (2 ^ 2) ^ 3
→ 0 ^ 0 ^ 3
→ 3

Все числа с чётным количеством исчезают.
Остаётся только то, у которого нечётное.