* William:[color=blue]
> 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."[/color]
What is the C++ question?
[color=blue]
> 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.[/color]
Try posting this in [comp.programming].
It's off-topic in [comp.lang.c++].
--
A: Because it messes up the order in which people normally read text.
Q: Why is it such a bad thing?
A: Top-posting.
Q: What is the most annoying thing on usenet and in e-mail?
