Find the Unique Number

You are given an array of n integers where every element appears exactly twice except for one unique element that appears only once. Your task is to find and output this unique number.

The solution must run in \(O(n)\) time and use \(O(1)\) extra space. A common approach is to use the bitwise XOR operation which has the property that \(a \oplus a = 0\) and \(a \oplus 0 = a\).

inputFormat

The first line contains an integer n representing the number of elements in the array. The second line contains n space-separated integers.

outputFormat

Output a single integer which is the unique number in the array.

5
4 1 2 1 2

4