Finding unpaired element in an array-CodePudding

So I have just started self learning algorithms by working through some sample questions I found (where you can check your solution's correctness and time complexity), and am a little confused by one question in particular.

In this question, I am given an array with an odd number of integer elements, where each element of the array can be paired with another element that has the same value, except for one element that is left unpaired. The question is asking me to find this unpaired element. The function I tried using is below in python;

def solution(A):
    
    N = len(A)   # constant
    if N == 1:   # constant
        return A[0]

    mergesort(A)   # NlogN

    if A[-1] != A[-2]:  # constant
        return A[-1]

    for i in range(0,N-1,2):   # apparently not linear?
        if A[i] != A[i 1]:
            return A[i]

Why this is O(N^2), rather than O(NlogN)?

The only reason I can think of is that the comparison of A[i] and A[i 1] is itself O(N), but I don't see why it wouldn't be constant.

Any help would be greatly appreciated, thanks heaps for reading!

CodePudding user response：

As Abhinav Mathur stated in the comments, it's likely that that your algorithm needs to be linear, rather than O(n log n).

Here's a solution that runs in linear time that leverages the XOR operation and the following properties of the operation:

XOR is commutative. That is, x ^ y = y ^ x.
Any number XOR'd with itself is 0. That is x ^ x = 0.
Any number XOR'd with 0 is itself. That is, x ^ 0 = x.

If we XOR all the numbers together, all of the numbers that appear twice will produce 0 in our XOR result. Whenever we XOR a zero value with the number that only appears once, we get the number that only appears once.

So, our answer is the result of XORing all the numbers in the array together:

def solution(A):
    result = 0
    for item in A:
        result ^= item
    return result

or if you like one-liners, use functools.reduce():

from functools import reduce

def solution(A):
    return reduce(lambda x, y: x ^ y, A, 0)

If we assume that the XOR operation takes constant time, then this algorithm runs in linear time.

You could also solve this using a hashset or collections.Counter(), but those will use a linear amount of memory. This approach uses constant memory.