Find value that occurs in odd number of elements I am trying to solve the following exercise using Javascript:

A non-empty array A consisting of N integers is given. The array contains an odd number of elements, and each element of the array can be paired with another element that has the same value, except for one element that is left unpaired.

For example, in array A such that:

  A[0] = 9  A[1] = 3  A[2] = 9
  A[3] = 3  A[4] = 9  A[5] = 7
  A[6] = 9


the elements at indexes 0 and 2 have value 9,
the elements at indexes 1 and 3 have value 3,
the elements at indexes 4 and 6 have value 9,
the element at index 5 has value 7 and is unpaired.

I have written the following code.

function solution(A) {        
    var pop;

    if(!A.length)
        return 0;

    while(A.length){
        pop = A.shift();            
        let pos = A.indexOf(pop);
        if(pos &gt;-1){
            A.splice(pos,1);                
        } else {
            return pop
        }
    }
    return pop;
}


The correctness seems to be fine but it fails the performance test. The order shown is O(N**2).


Any explanation why it shows exponential timing (I have not used any
nested loops)?
Any suggestions on what would be the optimized code which will run on O(N) having space complexity O(1)?
The solution with an O(N) time complexity with O(1) space is a little bit hacky. The solution is to xor each number together. some important properties of xor are:


xor of two identical numbers is zero.
xor of any number and zero is the number.
xor is commutative.
xor is associative.


example:

A = [9, 3, 9, 3, 9, 7, 9]

the solution to this example is:

  (((((9^3)^9)^3)^9)^7)^9
= 9^3^9^3^9^7^9              (4)
= 9^9^9^9^3^3^7              (3)
= (9^9)^(9^9)^(3^3)^7        (3)
= 0^0^0^7                    (1)
= 7                          (2)