Find the Single Number

Given a non-empty array of integers, every element appears exactly twice except for one element which appears only once. Your task is to find and return the element that appears once.

This can be solved using the bitwise XOR operation. Recall that for any integer a, a ⊕ a = 0 and 0 ⊕ a = a. Thus, by XOR-ing all the numbers, the pairs cancel out and only the unique number remains. Formally, if the array is \(A = [a_1, a_2, \dots, a_n]\), then the answer is:

[ a_1 \oplus a_2 \oplus \cdots \oplus a_n ]

where \(\oplus\) denotes the bitwise XOR.

inputFormat

The first line of input 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 element that appears only once in the array.

3
2 2 1

1