Find the Element That Appears Once in an List Where Every Other Element Appears Twice

In this tutorial, we will write the Python program to find an element that appears once in list. We have given an list that contains integer values, where all numbers occur twice except one number which occurs once. We need to find that unique number in O(n) time & constant extra space. For example -

Example -

Approach - 1: Brute-force

In this approach, we can indeed check every element to see if it appears only once. Once we find such an element, we can return it. Let's understand the following example.

Example -

Output:

Element that appears once: 1

Explanation -

In the above code, the find_single_element() function iterates through the input list and uses the count method to count the occurrences of each element. If it finds an element with a count of 1 (indicating it appears only once), it returns that element as the result.

While this approach works, it has a time complexity of O(n²) because the count method itself iterates through the list for each element. Therefore, it may not be efficient for large lists.

Now, we will solve this problem using the hash technique.

Approach - 2: Using Hashing

We can solve this problem using a hash table (dictionary in Python) to efficiently track the counts of each element. Following is the example:

Example -

Output:

Element that appears once: 1

Explanation -

In the code, we use a dictionary (element_counts) to store the counts of each element in the list. We iterate through the list, and for each element, we either increment its count in the dictionary if it already exists or add it to the dictionary with a count of 1 if it doesn't exist.

After counting all the elements, we iterate through the dictionary to find the element with a count of 1, indicating that it appears only once in the list.

This approach has a time complexity of O(n) because it iterates through the list once and uses a dictionary for efficient element counting. However, this solution works best but requires extra space.

Approach - 3: Using XOR

This approach is highly efficient, working in O(n) time complexity and requiring minimal extra space.

Below is the explanation how it works -

• XOR of a number with itself is 0: When you XOR a number with itself, the result is always 0. This property is key to the solution.
• XOR of a number with 0 is the number itself: When you XOR a number with 0, you get the original number back.

We will follow the below steps to find the elements.

1. Initialize a variable result to 0. This variable will hold the XOR result of all the elements in the list.
2. Iterate through the entire list.
3. This effectively accumulates the XOR of all the elements in the list into result.
4. After the loop, the result variable will contain the XOR of all the elements. Due to the XOR properties mentioned earlier, all elements that appear twice will cancel each other out, resulting in 0. Only the element that appears once will remain in result.
5. Return the value of result, which is the element that appears once.

Let's understand the following example -

Example -

Output:

Element that appears once: 1

Approach - 4 Using Binary Search Algorithm

Solving this problem using the binary search algorithm is not straightforward, as binary search is typically used for problems that involve sorted lists or have a defined order. However, we can use a modified binary search approach with some preprocessing to achieve this.

Here's a step-by-step solution using binary search:

1. Sort the given list: To make the binary search feasible, we need to sort the list first. Sorting takes O(n log n) time in the worst case.

2. Perform binary search:

- Initialize two pointers, low and high, to point to the first and last elements of the sorted list, respectively.

- While low is less than or equal to high, do the following:

- Calculate the middle index as `mid = (low + high) // 2`.

- Check if mid is even (i.e., list[mid] == list[mid + 1]). If it is, it means the unique element is on the right side of mid, so update low to mid + 2.

- If mid is odd (i.e., list[mid] != list[mid + 1]), it means the unique element is on the left side of mid, so update high to mid.

- After the loop, low will point to the unique element in the list.

3. Return list[low] as the result.

Here's the code implementing this approach:

Example -

Output:

Element that appears once: 1

This binary search approach, with the preprocessing step of sorting, can find the single-occurring element in O(log n) time complexity. However, it requires sorting, which takes O(n log n) time, resulting in a total time complexity of O(n log n).

Conclusion

We explored multiple approaches to find the element that appears once in an list where every other element appears twice. The brute-force approach, though simple, has a time complexity of O(n²) and may not be efficient for large lists. The hashing approach offers a time-efficient solution with a time complexity of O(n) but requires extra space. The XOR-based approach stands out as the most efficient, operating in O(n) time complexity and utilizing minimal extra space. Lastly, we discussed a binary search approach, which, while achieving O(log n) time complexity, necessitates sorting, resulting in an overall time complexity of O(n log n). The XOR approach remains the best choice for both time and space efficiency.