Algorithm Design and Analysis :: Blog :: Determine duplicate numbers in array

Q: Given an array of size N in which every number is between 1 and N, 

determine if there are any duplicates in it.

Ans: I'll try to do it in O(N) w/o using any additional memory. The key is

to use content of the array as index into array, checking in O(1) if 

that number has been seen already.

bool HasDups(int * a, int N)
{ 
	bool fHasDup = false;
	for (int i = 0; i < N; i++) {
		int index = a[i] % N;
		if (a[index] > N) {
			fHasDup = true;
			break;
		}
		a[index] += N;
	}
	
	//restore the array
	for (int j = 0; j < i; j++)
		if (a[j] > N) a[j] %= N;

	return fHasDup;
}