Find the Unique Number

You are given a list of integers in which every element appears exactly twice except for one element that appears only once. Your task is to find and output the unique element.

The problem can be solved in O(n) time using bitwise XOR operation. Recall that for any integer a, we have: \(a \oplus a = 0\) and \(0 \oplus a = a\). Using these properties, the XOR of all numbers gives the unique number.

inputFormat

The first line of input contains an integer \(n\) representing the number of elements in the list. The second line contains \(n\) space-separated integers. It is guaranteed that exactly one integer appears only once while every other integer appears exactly twice.

outputFormat

Output a single integer which is the unique element in the list.

3
2 2 1

1