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 that single element.

The solution must run in linear time, i.e., \(O(n)\) where \(n\) is the number of elements, and use constant extra space. A common strategy to solve this problem is to use the bitwise XOR operation, as it has the properties \(a \oplus a = 0\) and \(a \oplus 0 = a\) for any integer \(a\).

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 which are the elements of the list.

outputFormat

Output the unique number, i.e. the number which does not have a duplicate in the list.

1
1

1