Bit Manipulation
XOR and self-cancellation
One property does all the work: anything combined with itself vanishes.
Key idea
Three properties, and everything follows
Anything combined with itself gives zero. Anything combined with zero is unchanged. The operation does not care about order or grouping.
Together those mean that combining a whole collection cancels every value appearing an even number of times and leaves whatever appears an odd number of times. That single consequence is the entire technique.
Each of the three is worth seeing on its own before relying on the consequence.
Tip
Order-independence is what makes it usable
Because grouping and order do not matter, the values can arrive in any sequence and the running combination is always correct. No sorting, no bookkeeping, constant space.
That is why this beats a hash map for the odd-one-out question: the map is O(n) space and this is O(1). When a problem demands constant space and mentions pairs, this is what it is asking for.
Key idea
Combining two collections to find a difference
The same property finds a missing element. Combine every value that should be present with every value that is present. Everything appearing in both cancels, and only the missing one survives.
That works whatever the two collections are, which makes it more general than it first appears: it finds the one element by which two multisets differ.
Neither collection has to be materialized either. If the values that should be present follow a rule, they can be combined in the same loop that reads the ones that are, which is what keeps the space constant rather than merely small.
Tip
The arithmetic alternative
Subtracting the actual total from the expected total finds the same missing value, and the expected total has a closed form so it needs no loop at all.
In a language with fixed-width integers, the sum can overflow on large inputs where the combination cannot. Python has no such limit, so both are safe here, and naming the difference is a good remark to make.
Why it works
When values do not pair up evenly
The technique finds one odd-count value. If two values appear an odd number of times, the result is their combination rather than either of them, which is not directly useful.
Recovering both is possible: any set bit in that combination is a position where the two differ, so partitioning the values by that bit separates them into two groups each containing one of them. That is a genuinely nice extension and worth knowing exists, though no problem here needs it.
Cost
Cost
One pass, one integer, so O(n) time and O(1) space. That constant space is usually the reason the problem is being asked.
A hash map or a set solves both problems here and uses O(n) space. Offer that first if it comes to you faster, then give this one as the constant-space improvement.
Predict the output: what survives
Type the three values this prints, separated by single spaces.
Single Number
Read the constraints first and let them tell you what complexity is expected. Derive the approach, implement it, run the tests, and submit when it passes.
Missing Number
Read the constraints first and let them tell you what complexity is expected. Derive the approach, implement it, run the tests, and submit when it passes.