426,011 Members | 1,000 Online
+ 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
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 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.