поиск непарного целого числа с O (logN)

Question

Я наткнулся на этот тест:

Дан непустой массив A, состоящий из N целых чисел.
Массив содержит нечетное количество элементов, и каждый элемент массива может быть в паре с другим элементом, имеющим такое же значение, за исключением одного элемента, который остался непарным.
EG
A = [9,3,9,3,5,7,5] // 3, 5 и 9 можно объединить в пару, а 7 оставить в покое.
Напишите эффективную функцию, которая, учитывая массив A из N целых чисел, возвращает значение непарного элемента.
Примечание:
1) N - нечетное целое число в диапазоне [1..1,000,000];
2) каждый элемент массива A является целым числом в диапазоне [1..1,000,000,000];
3) все значения, кроме одного, встречаются в A четное количество раз.

вот мое решение, которое не считается эффективным, потому что его сложность равна O (N ** 2).

function solution(A) {
    let res;
    A.sort();
    //3,3,7,9,9,9,9    
    while(A.length>1) {
        if(A[0] === A[1]) {
            A.shift();
            A.shift();
        } else {
            res = A[0];
            break;
        }
    }
    res = A.length === 1 ? A[0] : res;
    return res;
} 

Как мне улучшить это здесь?

Вот неудачные тесты:

Answer 1

Я уже видел эту проблему, вы можете выполнить XOR для всех чисел в массиве, и конечным результатом будет единственное число, не связанное с парой. Это решение довольно быстрое и должно удовлетворять вашим требованиям к скорости,

Small basi c, пример:

console.log (12 ^ 3 ^ 3 ^ 12 ^ 4 ^ 5 ^ 4)

Приведенный выше код вернет 5 (это единственное число без пары в моем примере).

Answer 2

спасибо @ Bindy1

вот код, который я написал на основе вашего предложения.

function solution(A) {
    let mySet = new Set();
    let auxFn;
    A.forEach( item => {
        auxFn = mySet.has(item) ? 'delete' : 'add';
        mySet[auxFn](item);
    });
    return [...mySet][0];
}