- a single duplicate number exists
- multiple duplicate numbers exist

# 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

Subscribe to:
Post Comments (Atom)

## 3 comments:

For single duplicate numberIn 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

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

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

Post a Comment