Find the Single Number

Given an array of integers of odd length in which every element appears twice except for one, your task is to find that single non-duplicate element. This problem requires an efficient solution, and you are expected to perform bitwise manipulation (using the XOR operation) to solve it.

Note: The input is read from standard input (stdin) and the output is printed to standard output (stdout).

Mathematical Insight: Using the property of XOR, i.e., \(a \oplus a = 0\) and \(a \oplus 0 = a\), you can cancel out the duplicates and obtain the unique number.

inputFormat

The first line of input contains a single integer \(n\) (where \(n\) is odd and at least 1) representing the number of elements in the array.

The second line contains \(n\) space-separated integers. In the given array, every integer appears exactly twice except for one.

outputFormat

Output a single integer which is the non-duplicate element from the array.

5
4 1 2 1 2

4