I would appreciate your help on the following programming questions:

1. Given an array of length N containing integers between 1 and N,

determine if it contains any duplicates.

HINT: [Is there an O(n) time solution that uses only O(1) extra space and

does not destroy the original array?]

The solution is:

http://domino.research.ibm.com/Comm/...nuary2004.html
but I don't understand what they meant by "Let f(x) be the location of the

array at address x."

2. Sort an array of size n containing integers between 1 and K, given a

temporary scratch integer array of size K.

HINT: Compute cumulative counts of integers in the auxiliary array. Now

scan the original array, rotating cycles!

3. An array of size k contains integers between 1 and n. You are given

an additional scratch array of size n. Compress the original array by

removing duplicates in it. What if k << n?

HINT: Can be done in O(k) time i.e. without initializing the auxiliary

array!

Any solutions, partial solutions, or algorithms to the above problems is

greatly appreciated.

William