在数组中寻找唯一未配对的元素

1. Overview

In this article, we’ll discuss the problem of finding the only unpaired element in an array. We’ll start by explaining the problem with an example. After that, we’ll present three different approaches to solving it.

2. Defining the Problem

Given an array of size , where is an odd number, each element inside the array is given twice, except for one element, which is only presented once in the array. Our task is to find the element that is presented once and thus can’t be paired with any other element.

Let’s take the following array as an example:

Let’s try to pair the elements in this array, each element with another one that has the same value:

As we can see, the values 4, 3, and 1 were paired with the same color because there are two elements of each of them. However, the value 2 was left unpaired, as there’s only one element of that value.

Thus, the answer to our example is 2.

Now that we explained the problem, let’s discuss the different approaches to solving it.

3. Naive Approach

In the naive approach, we try to search the array linearly for the pair of each element. Once we find an element that doesn’t have a pair, we declare it as the answer to the problem.

Let’s take a look at the implementation:

algorithm NaiveApproach(A, N):
    // INPUT
    //     A = an array of integers
    //     N = the size of the array
    // OUTPUT
    //     Returns the only unpaired element in A

    for i <- 1 to N:
        isPaired <- false
        for j <- 1 to N:
            if i != j and A[i] = A[j]:
                isPaired <- true
                break
        if isPaired = false:
            return A[i]

    return -1

We start by iterating over all the elements of the array. For each element, we set the value to false, indicating that the current element isn’t paired yet. Next, we iterate over the array to search for a pairing of the element that is found at a place , which is different from . If we find one, we set the value to true and break the inner loop.

Once the inner loop is finished, we check the value of . If it remained , then the current element was unpaired. Thus, we return its value as the answer to the problem.

On the other hand, if the algorithm finished without finding any element that is unpaired, we return , indicating a wrong input array.

The complexity of this approach is , where is the size of the array.

4. Map Approach

The main idea in this approach is to iterate only once over the array and store the number of occurrences of each element. To do this, we need to use a data structure such as a map.

Take a look at the implementation:

algorithm MapApproach(A, N):
    // INPUT
    //     A = an array of integers
    //     N = the size of the array
    // OUTPUT
    //     Returns the only unpaired element in A

    map <- create an empty map
    for i <- 1 to N:
        map[A[i]] <- map[A[i]] + 1
    for element in map:
        if element.value = 1:
            return element.key

    return -1

We declare a which will hold the number of occurrences of each value. Next, we iterate over the map and increase the occurrences of the current element by one inside the map.

Once we’re done, we iterate over the map to check all the different values we got. The element which only occurred once is the element that is unpaired. Thus, we return such an element if we find it. Otherwise, we return , indicating an incorrect input.

The complexity of this approach is , where is the size of the array.

This complexity is assuming a constant factor for the time complexity when dealing with the map. However, we can find a better approach that removes the complexity of dealing with a map, which is the XOR approach.

5. XOR Approach

5.1. Main Idea

The idea behind using the bitwise XOR operation is that we can use the following facts:

   

   

   

where is the logical bitwise XOR operation.

Assume that the array contains elements from (which is the unpaired value) to . Let’s calculate the XOR of all the elements inside the array :

   

Using the first fact, we can order the elements to make the equal ones become adjacent, such as:

   

Next, using the second fact, we can perform the XOR operation on each two adjacent equal elements to get zero:

   

Finally, using the third fact, we can get the final result:

   

In conclusion, the final result of the XOR operation is the unpaired element.

5.2. Implementation

Let’s have a look at the implementation:

algorithm XORApproach(A, N):
    // INPUT
    //     A = an array of integers
    //     N = the size of the array
    // OUTPUT
    //     Returns the only unpaired element in A

    answer <- 0
    for i <- 1 to N:
        answer <- answer XOR A[i]

    return answer

We declare equal to zero, which will hold the result of the XOR operation. Next, we iterate over all the elements inside the array. For each element, we perform an XOR with the previous value of (which contains the XOR of the previous elements) and store the result back inside the variable .

Finally, we return the value of , which contains the result of performing XOR operation to all the elements inside the array. At the same time, it represents the value of the only unpaired element.

The complexity of this approach is , where is the size of the array.

6. Conclusion

In this tutorial, we presented the problem of finding the only unpaired element in an array. Firstly, we described the problem and provided an example that explains it. Secondly, we showed three different approaches to solving the problem and compared their complexities.