Find repetition in O (n) and constant space

Question

Possible duplicate:
The question with an easy interview was complicated: data numbers 1..100, find the missing numbers
Find missing and repeating elements in an array in linear time and constant space

I saw an interesting question on one forum.

you have 100 elements from 1 to 100, but by mistake one of these numbers overlaps with the other, repeating itself. For instance. 1,99,3, ..., 99100 Array not in sorted format, how to find duplicate number?

I know that a Hash can do this O (n) time and O (n) space, I need O (1) space.

Answer 1

We can do this in O (n) and constant space:

• For each element, calculate index = Math.abs(a[i]) - 1
• Check the value of index
  • If it is positive, multiply by -1, i.e. make it negative.
  • if it is negative, return ( index+1 ) as the answer, as this means that we have seen this index before.

""

 static int findDup(int[] a){ for(int i=0;i<a.length;i++){ int index = Math.abs(a[i]) - 1; if(a[index] < 0) return index+1; else a[index] = -1 * a[index]; } return -1; } 

Answer 2

Calculate two amounts: the sum and the square sum.

In your example:

 sum = 1+99+3...+100 sq_sum = 1^2+99^2+3^2+...+100^2 

Suppose y replaced x in a sequence.

 sum = n(n+1)/2 -y+x. sq_sum = n(n+1)(2n+1)/6 -x^2 +y^2 

Now, decide for x and y.

Constant space and time O (n).

How to solve for x and y

From the equation:

 x = sum - n(n+1)/2 +y 

Replace this in the second equation:

 sq_sum = n(n+1)(2n+1)/6 -(sum - n(n+1)/2 +y)^2 +y^2 

Note that y ^ 2 is canceled, and you remain a linear equation with one unknown: y. Decide!

Answer 3

A new approach. Let m be the missing number and r be the repeating number. After going through the array once, let X be the result of XOR inputting the array entries along with indices 1 - n . Then X = m XOR r . In particular, it is not 0 . Let b be any nonzero bit of X (you only need to select one, and one exists, since X not 0 ). After going through the array, let Y be the result of XOR inputting the array entries and indices 1 to n , where bit b is 0 and let Z be the result of XOR entering the array entries and indices 1 to n , where bit b is 1 . Then Y and Z save m and r , so all that remains is to make the final pass to see what is in the array.

Total area: 4 (or 3 if you reuse X for b )

Total time: 7 passes (or 3 if you are doing indexes simultaneously with an array and calculating Y and Z at the same time.

Therefore, O(1) space and O(n) time.

Answer 4

Calculate the sum of all integers. Calculate int p = sum% 100 100 - p - answer