Найти число с четным числом вхождений
Дан массив, в котором число вхождений каждого числа нечетное, за исключением одного числа, чье количество вхождений является четным. Найти номер с четными вхождениями.
например
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? Если да, то как?