An interesting problem.
If the array has signed integers, I believe that this is possible in O (n) time and O (1) space without overflow, assuming that the length is small enough for this to happen.
The basic idea is as follows:
We have n numbers. Now, dividing these numbers by n + 1, we get n residues. Therefore, at least one of the residues in {0,1,2, ..., n} must be absent (say r). We fill the array with numbers whose remainders are r.
First, add a multiple of n + 1 to all negative numbers to make them positive.
Then we go to the array and find the remainder of each number with n + 1. If the remainder is r, we set a [r] as -a [r] if a [r] is positive. (If we meet negative numbers when walking, we use the negative version when taking the remainder).
We also have an extra int for the remainder = n.
At the end, we again massage the array to see if there are any positive numbers (there will be one, or an extra int for the remainder = n will be canceled).
Once we have a remainder, it is easy to generate n numbers with this remainder. Of course, we can always generate only one number and fill it with the fact that the problem never spoke about unique numbers.
If the array had unsigned integers, we could probably still do this with better accounting.
For example, we could try to use the first n / logn integers as our bitarray to indicate which residuals were noticed, and use some additional O (1) integers to temporarily hold the numbers.
For example, you do tmp = a [0], find the remainder and set the corresponding bit [0] (after you first set it to zero). tmp = a [1], dial bit, etc. We will never overwrite a number before we need it to find its remainder. Strike>