CareerCup

using Hash table is not right approach when we have million of numbers,.,,,,,think

First solution is to create a hash table of Integer size. 0- 2pow 32 and initialize it by 0, whenever you get any no. check the value at that position, if it is 0, it is only the first time we have encountered that no. increment it and proceed.

This would have the Time Complexity as O(1) but has space contraints.

Implement a better way to make it Space efficient as well.

we can do it like this,

int nLength = array.Length();
for ( int nIndex = 0; nIndex < nLength; nIndex++ ) {
while ( arr[i] != i && arr[i] != arr[arr[i]] ) {
swap(arr[i], arr[arr[i]] );
}
}

for ( int nIndex = 0; nIndex < nLength; nIndex++ ) {
if ( arr[i] != i )
print(arr[i]);
}

Its obvious, that we need to go through all numbers atleast once to find out the duplicates.
If extra space is ok, use hashsets. they store unique elements:
int array[] = { 1, 2, 3, 6, 4, 1, 7, 8, 9, 3, 2, 2, 5, 3, 4, 3, 6, 4 };
Set<Integer> uniqueNums = new HashSet<Integer>(array.length);
Set<Integer> duplicates = new HashSet<Integer>();
for (int i = 0; i < array.length; i++)
{
if (uniqueNums.contains(array[i]))
{
//numbers can be duplicate more then twice, so store unique again
duplicates.add(array[i]);
}
else
{
uniqueNums.add(array[i]);
}
}
System.out.println("Duplicates: " + duplicates);

If no extraspace, then have to compromise of time. Sorting and finding out is the only key

if the numbers are in a range then we can use

boolean

array to find out the duplicates. Use numbers as the index of boolean array and mark as you traverse array.
If

boolean

array element is already

true

it is a duplicate.

How about this? Please let me know your views on this.
Implement Radix sort & then in linear time we can find the duplicates.

I solved it like this

public static void printDuplicates( int[] numbers ) {
		
		Arrays.sort( numbers );
	
		Set<Integer> set = new TreeSet<Integer>();
		for( int i=0; i<numbers.length-1; i++ ) {
			if( numbers[i+1] == numbers[i]) set.add(numbers[i]);
		}
		
		for( Integer i : set)
			System.out.println(i);
	}