CareerCup

Use Hash Map...
Say unique number of elements is k
Extra Memory O(k)
Time O(n)

Sort numbers and do it
Time to sort O(n log n)
No Extra memory required

Good Question..
Lemme give my view.. Every prgm either hv to compromise of Time or Space Complexity..

Algo:-
1> Space Compromise :-
a> Read a array and hash it.
b> Before putting into hash table check if that place is filled.
c> if Filled its duplicate else not keep it in there.

2> Time Compromise :-

Usual Sorting algo with little modification will work.
a> Pick an element search for its duplicity in the array with min complexity.

Is there any time constraint? If not, simply sort tha array and then look for the repeated elements -- O(n.log n).

how about constructing a heap out of this array and when inserting (shuffling) array items if you find what you have in hand is repeated item print it and continue in the same manor. heap construction takes o(n) so will this ...no need to use extra memory use the one array has...

1. Sort the array in nlogn time (in place). Find Duplicates in O(n) time. Overall 0(n lg n) time. -- Limited memory approach
2. Use Hash table to check if a number is already present. -- Unlimited memory approach.
3. Use distributed approach, lets say you have 10 machines, distribute the numbers as number % 10. And those 10 machines removes the duplicate among assigned number, Union of all those will be the distinguish numbers.
4. Another unlimited memory approach could be BloomFilter (conceptually similar to HashTable). But it save memory if the range of numbers is not too big with respect to the number of numbers. For 32 bit numbers. Memory requirement will be 4BG/8 = 256MB.

1. Merge sort
2. Heap sort

both O(n log n), heap sort requires no extra memory for array

In fact you can get it in O(n)
Maintain two numbers x and y and a temporary variable
while iterating through the array, temp= x^array[i]
if(temp==0), print that number.. else keep x=x^array[i] as it is
in order to see that the same number not to get printed store the printed number in y
temp = y^(printed number)
print the number only if temp!=0
Help this explains the algorithm!!