By using this site, you agree to our updated Privacy Policy and our Terms of Use. Manage your Cookies Settings.
426,011 Members | 1,000 Online
Bytes IT Community
+ Ask a Question
Need help? Post your question and get tips & solutions from a community of 426,011 IT Pros & Developers. It's quick & easy.

Array Programming Questions:

P: n/a
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

Jul 23 '05 #1
Share this Question
Share on Google+
4 Replies


P: n/a
William wrote:
I would appreciate your help on the following programming questions:

[...]


This is a C++ language newsgroup. I recommend asking your programming
questions in a general programming newsgroup: comp.programming.

V
Jul 23 '05 #2

P: n/a
* 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/...nuary2004.html

but I don't understand what they meant by "Let f(x) be the location of the
array at address x."
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?
Jul 23 '05 #3

P: n/a
On 2005-05-26, William <wh******@student.cs.uwaterloo.ca> 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/
Jul 23 '05 #4

P: n/a
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/...nuary2004.html

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


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
kb******@gascad.at
Jul 23 '05 #5

This discussion thread is closed

Replies have been disabled for this discussion.