Find duplicates in an array

Given an array of size 'n', containing elements from 1 to 'n', find out if there are any duplicates in the array. Solve this, if
  • a single duplicate number exists
  • multiple duplicate numbers exist
 Source : CLRS & this blog question (that I did not get)

3 comments:

Madhur Kumar Tanwani said...

For single duplicate number

In O(n) time, find the sum of the array elements (say sum) and the sum of the squares of the array elements (say ssum).


We know sum of first 'N' natural numbers is N(N-1)/2 (say osum) and the sum of squares of first 'N' natural numbers is N(N+1)(2N+1)/6 (say ossum).

Hence,
1 + 2 + .... x + y + .. n = osum
1 + 2 + .... x + x + .. n = sum

1^2 + 2^2 + .... + x^2 + y^2 + ... + n^2 = ossum
1^2 + 2^2 + .... + x^2 + x^2 + ... + n^2 = ssum

Subtracting the equations,
y -x = osum - sum
y^2 - x^2 = ossum - ssum

Which can be solved to find y and x

Madhur Kumar Tanwani said...

For multiple duplicates (I think), sort the array and traverse the array to find the duplicates.

Madan Kumar said...

main:
For i in 1 to N do
fix-cycle(i)

fix-cycle:(i)
if A[i] == i
then return
else if A[i] == A[A[i]]
then print "Duplicate found - " + A[i]
return
else
swap A[i] with A[A[i]]
fix-cycle i

 
Stats