Найти число с четным числом вхождений

Дан массив, в котором число вхождений каждого числа нечетное, за исключением одного числа, чье количество вхождений является четным. Найти номер с четными вхождениями.

например

1, 1, 2, 3, 1, 2, 5, 3, 3

Вывод должен быть:

2

Ниже приведены ограничения:

Numbers are not in range. Do it in-place. Required time complexity is O(N). Array may contain negative numbers. Array is not sorted.

Из-за вышеуказанных ограничений все мои мысли потерпели неудачу: сортировка на основе сравнения, сортировка по счету, BST, хеширование, перебор.

Мне любопытно узнать: сработает ли здесь XORing? Если да, то как?