Find the Unique Element in a Triply-Repeated Array

You are given an array of n integers. In this array, every element appears exactly three times except for one element, which appears only once. Your task is to identify that unique element.

The solution should run in linear time, i.e. \(O(n)\), and use constant space. A hint for an efficient solution is to leverage bitwise operations. You can maintain two counters, ones and twos, to track the bits that have appeared 3k+1 and 3k+2 times respectively. In particular, you can update the values as follows:

\[ \text{ones} = (\text{ones} \oplus \text{num}) \land \lnot\text{twos} \]
\[ \text{twos} = (\text{twos} \oplus \text{num}) \land \lnot\text{ones} \]

After processing all elements, \(\text{ones}\) will contain the unique element that appears exactly once.

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 element that appears only once.

4
2 2 3 2

3