array Puzzle

Discussion in 'C++' started by puzzlecracker, Jan 20, 2005.

  1. Given an array of size n and populated with consecutive integers from 1
    to n i.e. [1, 2...n-1, n] in random order. Two integers are removed,
    meaning zero is placed in their places. Give O (n) efficient algorithm
    to find them?
    puzzlecracker, Jan 20, 2005
    #1
    1. Advertising

  2. * puzzlecracker:
    > Given an array of size n and populated with consecutive integers from 1
    > to n i.e. [1, 2...n-1, n] in random order. Two integers are removed,
    > meaning zero is placed in their places. Give O (n) efficient algorithm
    > to find them?


    Are you sure this, uhm, "puzzle" is one you've made yourself?

    It seems designed to teach the student a particular technique
    and perhaps use of a particular standard C++ container.

    As a programming puzzle it's a bit more interesting (but still novice-
    level) if memory usage is restricted to O(1) except the original array
    itself, and for that I'm cross-posting this to [comp.programming], with
    follow-up there.

    --
    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, Jan 20, 2005
    #2
    1. Advertising

  3. puzzlecracker

    Phil Staite Guest

    How about something like this:


    #include<iostream>
    #include<vector>
    #include<algorithm>
    #include<iterator>


    typedef std::vector<int> iVec_t;
    typedef iVec_t::iterator iVec_i;

    int main( int argc, char* argv[] )
    {
    // load up a vec with numbers and shuffle them
    iVec_t v(20);
    for( iVec_i i = v.begin() ; i != v.end() ; ++i )
    *i = 1 + ( i - v.begin() );
    std::random_shuffle(v.begin(),v.end());
    // pick two and zero them out
    v[3] = v[15] = 0;
    // dump it for a peek
    std::copy(v.begin(),
    v.end(),
    std::eek:stream_iterator<int>( std::cout, " " ) );
    std::cout << std::endl;

    // use special knowledge of the data to perform a linear
    // time sort.
    for( int i = 0 ; i < v.size() ; ++i )
    {
    while( ( v != 0 ) && ( v != (i+1) ) )
    std::swap( v, v[v-1] );
    }

    for( int i = 0 ; i < v.size() ; ++i )
    if( v == 0 )
    std::cout << "Missing element " << (i+1) << std::endl;

    std::copy(v.begin(),
    v.end(),
    std::eek:stream_iterator<int>( std::cout, " " ) );
    std::cout << std::endl;

    return 0;
    }


    You make one linear pass through the vector and examine the element at
    each position. If it is 0, do nothing. If it is not, put it in the
    "right" place in the vector by swapping, and examine the element you
    swap in.

    It looks like it could be O(n2) but I would argue that it is not, that
    it is in fact linear. Worst case, say for the first element in the
    vector you end up examining and swapping every other element. So you've
    done order n compares (value to expected value in this position) and
    order n swaps. Now you proceed through the vector and find everything
    in place. So you do order n compares and no more swaps. Overall, you
    end up comparing each element twice, and moving it at most twice. So it
    is 2N... Then one more linear pass to find the zeros.
    Phil Staite, Jan 20, 2005
    #3
  4. puzzlecracker wrote:
    >
    > Given an array of size n and populated with consecutive integers from 1
    > to n i.e. [1, 2...n-1, n] in random order. Two integers are removed,
    > meaning zero is placed in their places. Give O (n) efficient algorithm
    > to find them?


    O(n) means the search time increases with the number of elements.
    Twice as many numbers - twice as much time.

    That should be easy: A simple loop should do

    void Delete2( int Array[], int n, int Number_to_Delete_1, int Number_to_Delete_2 )
    {
    for( int i = 0; i < n; ++i ) {
    if( Array == Number_to_Delete_1 ||
    Array == Number_to_Delete_2 )
    Array = 0;
    }
    }

    --
    Karl Heinz Buchegger
    Karl Heinz Buchegger, Jan 20, 2005
    #4
  5. puzzlecracker

    Howard Guest

    "puzzlecracker" <> wrote in message
    news:...
    > Given an array of size n and populated with consecutive integers from 1
    > to n i.e. [1, 2...n-1, n] in random order. Two integers are removed,
    > meaning zero is placed in their places. Give O (n) efficient algorithm
    > to find them?
    >


    Seriously now, where are you getting all these odd questions? I cannot
    believe you're making them up. Are they homework, some kind of home-study
    course, or a list of possible interview questions?

    In any case, how about you try to solve the problem yourself first, then
    post with any issues you have with your solution? Why should we waste our
    time? It's not like you're having a problem with the language that you need
    help with. Especially in this case. Besides, this question is asking for
    an algorithm, and has nothing to do with the C++ language. You could ask in
    a more general newsgroup, I suppose. But still, I think someone looking to
    hire a programmer would look for someone who could solve such things on
    their own, don't you?

    -Howard
    Howard, Jan 20, 2005
    #5
  6. puzzlecracker

    David Hilsee Guest

    "puzzlecracker" <> wrote in message
    news:...
    > Given an array of size n and populated with consecutive integers from 1
    > to n i.e. [1, 2...n-1, n] in random order. Two integers are removed,
    > meaning zero is placed in their places. Give O (n) efficient algorithm
    > to find them?


    std::vector<int> numbersSeen( n + 1 );
    for ( int i = 0; i < n; ++i ) {
    numbersSeen[ array ] = 1;
    }

    for ( int i = 1; i <= n; ++i ) {
    if ( numbersSeen == 0 ) {
    std::cout << i << " was removed from array" << std::endl;
    }
    }

    --
    David Hilsee
    David Hilsee, Jan 21, 2005
    #6
  7. puzzlecracker

    David Hilsee Guest

    "David Hilsee" <> wrote in message
    news:...
    [...]
    > std::vector<int> numbersSeen( n + 1 );


    std::vector<bool> would have been a better choice, of course.

    --
    David Hilsee
    David Hilsee, Jan 21, 2005
    #7
    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. Earl Teigrob
    Replies:
    3
    Views:
    6,635
    Nedu N
    Aug 6, 2003
  2. Lasse Edsvik

    Array puzzle

    Lasse Edsvik, Dec 3, 2004, in forum: ASP General
    Replies:
    0
    Views:
    99
    Lasse Edsvik
    Dec 3, 2004
  3. Lasse Edsvik

    Array puzzle

    Lasse Edsvik, Dec 3, 2004, in forum: ASP General
    Replies:
    3
    Views:
    109
    Ray Costanzo [MVP]
    Dec 3, 2004
  4. Gani Ruthellen

    array.each puzzle from new ruby-er

    Gani Ruthellen, Aug 7, 2007, in forum: Ruby
    Replies:
    6
    Views:
    131
  5. Tom P

    numpy masked array puzzle

    Tom P, Nov 17, 2013, in forum: Python
    Replies:
    1
    Views:
    64
    Joel Goldstick
    Nov 17, 2013
Loading...

Share This Page