Найти целое число, не встречающееся дважды в массиве

Question

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

Простым решением является сортировка массива, а затем проверка на отсутствие повторов. Но я ищу лучшее решение, которое имеет временную сложность O (n).

Answer 1

Вы можете использовать операцию "xor" для всего массива. Каждая пара чисел отменяет друг друга, оставляя вас с искомым значением.

int get_orphan(int const * a, int len)
{
    int value = 0;
    for (int i = 0; i < len; ++i)
        value ^= a[i];

    // `value` now contains the number that occurred odd number of times.
    // Retrieve its index in the array.
    for (int i = 0; i < len; ++i)
    {
        if (a[i] == value)
            return i;
    }

    return -1;
}