Find the single occurence of a element in the list of elements with twice repeative

In this post, we’ll solve an interesting problem where we need to find the single element that appears only once in a list of integers, while all other elements appear exactly twice.

Problem Explanation

Consider a list of integers where every element except one appears twice. We want to efficiently find the element that occurs only once. Here’s an example:

n = [23, 2, 2, 24, 7, 23, 5, 24, 5]

In this list, every number except 7 appears twice. Our goal is to find that single occurrence using an efficient algorithm.

Approach: Using XOR to Find the Single Element

We can solve this problem in linear time $O(n)$ and constant space $O(1)$ using the XOR (bitwise exclusive OR) operation.

How XOR Helps

1. XOR Basics:
   • XOR is a bitwise operation that compares the binary representation of two numbers.
   • The key property of XOR is that when you XOR a number with itself, the result is 0:
     $n \oplus n = 0$
   • XORing any number with 0 returns the number itself:
     $n \oplus 0 = n$
2. Eliminating Repeated Elements:
   • If you XOR all the elements in the list together, the repeated elements will cancel out (because $n \oplus n = 0$), leaving you with the element that occurs only once.

Example Walkthrough

Let’s walk through the list n = [23, 2, 2, 24, 7, 23, 5, 24, 5] step by step to see how XOR works: 

res = 0 (initial result)

res = res ^ 23 => 23
res = res ^ 2  => 21
res = res ^ 2  => 23
res = res ^ 24 => 15
res = res ^ 7  => 8
res = res ^ 23 => 31
res = res ^ 5  => 26
res = res ^ 24 => 2
res = res ^ 5  => 7

At the end of this process, the result is 7, which is the number that appears only once in the list.

Python Code Implementation

Now, let's write the code to implement this solution:

 

def find_single_occurrence(arr):

    # Initialize result to 0

    res = arr[0]

    # Iterate through the list and XOR each element with the result

    for i in range(1, len(arr)):

        res = res ^ arr[i]

    return res

# Input: a list of integers

n = list(map(int, input().split()))

# Finding the single occurrence element

single_element = find_single_occurrence(n)

# Output the result

print("The element that appears only once is:", single_element)

Input and Output

Input:
The input is a list of integers, where all elements except one appear exactly twice. For example:

23 2 2 24 7 23 5 24 5

Output:
The output is the element that appears only once:

The element that appears only once is: 7

How the Code Works

1. Initialization: We start with the first element in the list as the initial value of res (the result). This will be XORed with every other element in the list.

2. Iterating and XORing: For each element in the list, we perform an XOR operation with res. As discussed, this operation will cancel out the numbers that appear twice, leaving only the number that appears once.

3. Final Output: After all elements are XORed together, res will hold the value of the element that occurs only once, which we then print.