Array Programming Questions:

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

  1. William

    William Guest

    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 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
     
    William, May 26, 2005
    #1
    1. Advertising

  2. 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
     
    Victor Bazarov, May 26, 2005
    #2
    1. Advertising

  3. * 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
    > 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?
     
    Alf P. Steinbach, May 26, 2005
    #3
  4. 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
    #4
  5. 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 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
     
    Karl Heinz Buchegger, May 30, 2005
    #5
    1. Advertising

Want to reply to this thread or ask your own question?

It takes just 2 minutes to sign up (and it's free!). Just click the sign up button to choose a username and then you can ask your own questions on the forum.
Similar Threads
  1. Matt
    Replies:
    35
    Views:
    10,710
    George Neuner
    Jul 22, 2004
  2. Zygmunt Krynicki
    Replies:
    1
    Views:
    638
    Ivan Vecerina
    Oct 11, 2003
  3. Casey Hawthorne
    Replies:
    4
    Views:
    1,040
    Jarek Zgoda
    Aug 4, 2006
  4. sigi
    Replies:
    4
    Views:
    545
  5. Joe Mayo
    Replies:
    168
    Views:
    3,433
    David Thompson
    Oct 22, 2007
Loading...

Share This Page