- 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 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
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