void quicksort (int[] a, int lo, int hi)
{
//  lo is the lower index, hi is the upper index
//  of the region of array a that is to be sorted
    int i=lo, j=hi, h;
    int x=a[(lo+hi)/2];

    //  partition
    do
    {    
        while (a[i]<x) i++; 
        while (a[j]>x) j--;
        if (i<=j)
        {
            h=a[i]; a[i]=a[j]; a[j]=h;
            i++; j--;
        }
    } while (i<=j);

    //  recursion
    if (lo<j) quicksort(a, lo, j);
    if (i<hi) quicksort(a, i, hi);
}

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