Sum(Array) - 1000000(1000000 + 1)/2 = X
For the other part it's just
1000000(1000000 + 1)/2 - Sum(Array) = Y
EDIT: n*(n+1)/2 is the formula for the sum of the numbers from 1 to n
[1, 3, 3, 9, 42]
As for the solution, allocate 1,000,000 bits and do a "bucket sort". If the next number in the array is n, check if the nth bit is 1. If it is, you've found the integer appearing twice. If the nth bit is 0, change it to 1 and continue.
n is not an index... it's the last number. I wasn't explicit, sorry. :)
picture it like finding the area of a trinagle that is half of a square (long side goes from diagonally opposite corners)
formula for area of a square is n^2, so we need half that.
What about +n part of it? It is because we are dealing in discrete chunks, not smoothly continuous.
---
Alternately, imagine a series of children's blocks
1
2
3
now we have a 'triangle' with left side 3 high and bottom 3 wide. IF we make an identical triangle and rotate it round so that they fit together to make a rectangle, it looks like this
1 + 3
2 + 2
3 + 1
This makes a rectangle 3 x 4, and we should be able to figure out that this gives us an area of 12. So the original triangle ( 1,2,3 ) gives us half that and thus the sum from 1 to 3 is 6.
So the pattern for summing the numbers 1 through N is to take a square of length N, add 1 to one of its sides, so it has sides of length N and N+1, and then find the area (which is always N^2 + N) and then halve that.