I would xor all of the numbers, and xor that with what the xor of the full list should have been. (That xor depends on N and is not hard to figure out.)
This works because xor has the following properties:
a xor b = b xor a
(a xor b) xor c = a xor (b xor c)
- 0 is the identity:
a xor 0 = a
- self-negating: `a xor a = 0
Better yet, it does it without ever changing how many bits you have in your representation. And xor happens to be one of the fastest operations in a computer.
Therefore the result of that computation is the same as you would get if you paired each number in the list with a copy of itself, xored them all together, then the extra number that was inserted by mistke. But that turns into 0 xored with itself a bunch of times then xored with the extra number. Which all becomes just the extra number.