Old but gold

Old but gold

Let's discuss a programming task. You have a bunch of numeric pairs like 5, 5, 7, 7, 2, 2 and one unique number, like 13. You mix everything into one array and shuffle it. Now you have something like [7, 2, 13, 5, 2, 7, 5]. Let n be the number of elements and let it be huge, like 100000000. Numbers are 32- or 64-bit wide. The task is to find the unique number. In our case it would be 13.

Feel free to share in comments time and memory complexities of your approach to this problem. It would be like T=O(...); M=O(...)

I think it would be fun to collect options for a few days and then compare algorithms.