Optimize Time Complexity For Odd Occurrences In Array

Question

I have this code that pairs same elements in an array, with the expectation that the array will have an odd length and it should return the only element that couldn't get a pair. So I wrote the code just well, and it works fine for smaller arrays, but with very large big integers of over 1 billion, the time complexity became O(N**2) and then the need to refactor my code to get a much better performance for large arrays and large array elements. Here is my code below;

function solution(A) {
if(!Array.isArray(A)) return 0;

var temp = new Array(A.length);
var position = 0;

for(let i=0; i<A.length; i++){
    if(temp.includes(A[i])){
        position = temp.indexOf(A[i]);
        index = A.indexOf(A[i]);
        delete temp[position];
        delete A[index];
        delete A[i];
    }else{
        temp[i] = A[i];
    }
}

for(let j=0; j<A.length; j++){
    if(A[j] !== undefined) return A[j];
    else continue;
}
}

To test it, source data can look like [2,3,6,7,3,5,5,6,2] and it will give an output of 7. But when the array is so large up to [1,2,....] with length n = n=999,999, or n = 5000,000,000, the time complexity increases exponentially.

Answer 1

We can try to find odd occurrences for one iteration by using great features of object. Object is key - value pair. So access to object key is O(1). So when we meet the same element, then we just increment value:

const hashMap = arr.reduce((a, c)=> {
  a[c] = a[c] || 0;
  a[c] += 1;
  return a;
},{})
const result = Object.keys(hashMap).filter(key => hashMap[key] === 1);

An example:

let arr = [2, 3, 6, 7, 3, 5, 5, 6, 2];

const hashMap = arr.reduce((a, c)=> {
  a[c] = a[c] || 0;
  a[c] += 1;
  return a;
},{})
const result = Object.keys(hashMap).filter(key => hashMap[key] === 1);

console.log(result);

Answer 2

My two 100% JavaScript solutions with optimized time complexity. The first one is using Set:

function solution(A) {

    const pairs = new Set();

    for (const num of A) {
        if (pairs.has(num)) {
            pairs.delete(num);
        } else {
            pairs.add(num);
        }
    }

    const [unpaired] = pairs;
    return unpaired;

}

The second one is using bitwise XOR:

function solution(A) {

    let unpaired;

    for (const num of A) {
        unpaired ^= num;
    }

    return unpaired;

}