CareerCup

Good one. taking value as array index is the basis of hashing technique.

how abt hash table

1 3 4 2 3

Marking a[1] -ve ==> 1 -3 4 2 3
Marking a[3] -ve ==> 1 -3 4 -2 3
Marking a[2] -ve ==> 1 -3 -4 -2 3
Marking a[4] -ve ==> 1 -3 -4 -2 -3
now sees a[3] is already minus. 3 is a duplicated value

but this will help only max number in array is less than array range can we have any better solution?

if values are from 0 to n - 1 XORing is a better technique.

Any comparison algorithm can't have complexity better than O(nlogn) in this case.
To achieve O(nlogn) complexity, first sort the array by an O(nlogn) method and check for duplicates by iterating the array.

To achieve O(n) complexity, we can use hashing.

Hey any openings in qualcomm for freshers in India????

If the array is of length n and contains elements between 0 to n - 1 then we can do it by sequentially traversing the array and making elements -ve. If we find an already marked -ve element then that is duplicate

1 3 4 2 3

Marking a[1] -ve ==> 1 -3 4 2 3

Marking a[3] -ve ==> 1 -3 4 -2 3

Marking a[4] -ve ==> 1 -3 4 -2 -3

Marking a[2] -ve ==> 1 -3 -4 -2 -3

See that a[3] is already -ve => 3 is duplicate element