array Puzzle

[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?

[Alf P. Steinbach]

Re: array Puzzle

* puzzlecracker:[color=blue]
> 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?[/color]

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.programmin g], 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?

[Phil Staite]

Re: array Puzzle

How about something like this:


#include<iostre am>
#include<vector >
#include<algori thm>
#include<iterat or>


typedef std::vector<int > iVec_t;
typedef iVec_t::iterato r 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_shu ffle(v.begin(), v.end());
// pick two and zero them out
v[3] = v[15] = 0;
// dump it for a peek
std::copy(v.beg in(),
v.end(),
std::ostream_it erator<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[i] != 0 ) && ( v[i] != (i+1) ) )
std::swap( v[i], v[v[i]-1] );
}

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

std::copy(v.beg in(),
v.end(),
std::ostream_it erator<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.

[Karl Heinz Buchegger]

Re: array Puzzle

puzzlecracker wrote:[color=blue]
>
> 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?[/color]

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_Delet e_1, int Number_to_Delet e_2 )
{
for( int i = 0; i < n; ++i ) {
if( Array[i] == Number_to_Delet e_1 ||
Array[i] == Number_to_Delet e_2 )
Array[i] = 0;
}
}

--
Karl Heinz Buchegger
kbuchegg@gascad .at

[Howard]

Re: array Puzzle


"puzzlecrac ker" <ironsel2000@gm ail.com> wrote in message
news:1106185457 .421254.282960@ c13g2000cwb.goo glegroups.com.. .[color=blue]
> 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?
>[/color]

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

[David Hilsee]

Re: array Puzzle

"puzzlecrac ker" <ironsel2000@gm ail.com> wrote in message
news:1106185457 .421254.282960@ c13g2000cwb.goo glegroups.com.. .[color=blue]
> 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?[/color]

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

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

--
David Hilsee

[David Hilsee]

Re: array Puzzle

"David Hilsee" <davidhilseenew s@yahoo.com> wrote in message
news:-r-dnRgPaa15z23cRV n-sg@comcast.com. ..
[...][color=blue]
> std::vector<int > numbersSeen( n + 1 );[/color]

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

--
David Hilsee