# Array Programming Questions:

Discussion in 'C++' started by William, May 26, 2005.

1. ### WilliamGuest

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/wwwr_ponder.nsf/solutions/January2004.html

but I don't understand what they meant by "Let f(x) be the location of the

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

William, May 26, 2005

2. ### Victor BazarovGuest

William wrote:
> I would appreciate your help on the following programming questions:
>
> [...]

questions in a general programming newsgroup: comp.programming.

V

Victor Bazarov, May 26, 2005

3. ### Alf P. SteinbachGuest

* William:
> 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/wwwr_ponder.nsf/solutions/January2004.html
>
> but I don't understand what they meant by "Let f(x) be the location of the

What is the C++ question?

> 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.

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?

Alf P. Steinbach, May 26, 2005
4. ### Donovan RebbechiGuest

On 2005-05-26, William <> wrote:
> I would appreciate your help on the following programming questions:

Thanks, but I've already earned my degree. Good luck with yours. If you
have any specific C++ questions, you're welcome to post them here. But
don't expect anyone to do your homework for you.

Cheers,
--
Donovan Rebbechi
http://pegasus.rutgers.edu/~elflord/

Donovan Rebbechi, May 29, 2005
5. ### Karl Heinz BucheggerGuest

William wrote:
>
> 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/wwwr_ponder.nsf/solutions/January2004.html
>
> but I don't understand what they meant by "Let f(x) be the location of the

Array indexing.
If Numbers is the array, then f(x) would be Numbers[x] in C++ speak.
(Different programming languages have different syntax for array indexing)

--
Karl Heinz Buchegger

Karl Heinz Buchegger, May 30, 2005