question on array and number

i have one problem for example we have array

int a[]=new int[]{a1,a2,a3,a4,..........an}:

task is fill the same array by elements which are not in the array for example a={1,3,4,5,6,7} should be fill开发者_开发问答ed by any numbers {2,8,9,12,13,90}or others but not by elements which are in array this must not be{1,12,13,14,110} because 1 is in the array a thanks

Interesting problem.

If the array is of signed integers, I believe it is possible in O(n) time and O(1) space, with no overflows, assuming the length is small enough to permit such a thing to happen.

The basic idea is as follows:

We have n numbers. Now on dividing those numbers by n+1, we get n remainders. So atleast one of the remainders in {0,1,2, ..., n} must be missing (say r). We fill the array with numbers whose remainders are r.

First, we add a multiple of n+1 to all negative numbers to make them positive.

Next we walk the array and find the remainder of each number with n+1. If remainder is r, we set a[r] to be -a[r] if a[r] was positive. (If we encounter negative numbers when walking, we use the negated version when taking remainder).

We also have an extra int for remainder = n.

At the end, we walk the array again to see if there are any positive numbers (there will be one, or the extra int for remainder = n will be unset).

Once we have the remainder, it is easy to generate n numbers with that remainder. Of course we could always generate just one number and fill it with that, as the problem never said anything about unique numbers.

If the array was of unsigned integers, we could probably still do this with better book-keeping.

For instance we could try using the first n/logn integers as our bitarray to denote which remainders have been seen and use some extra O(1) integers to hold the numbers temporarily.

For eg, you do tmp = a[0], find remainder and set the appropriate bit of a[0] (after setting it to zero first). tmp = a[1], set bit etc. We will never overwrite a number before we need it to find its remainder.

Just get the highest and lowest number in the array, create a new array with elements from your lower bound value to n.

Obtaining the highest and lowest number can be done in the same loop.

Assuming 12,4,3,5,7,8,89, it'll detect 3 as the lowest, 89 as the highest value. It then creates a new array and fills it with 3..89; then discard the old array.