An array contains n - 2 distinct integers taken from 1..n. So exactly two numbers from that range are missing.
Find both of them in O(n) time and O(1) extra space, without modifying the array.
Example: n = 8, array [3, 1, 8, 6, 2, 7]. Missing: 4 and 5.
Hints, in white-on-white spirit:
- one equation is not enough for two unknowns
- you can get a second one cheaply
- there is also a bit trick if you prefer XOR over arithmetic
Spoilers in the replies, please mark them.