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]

* 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.

 

[Phil Staite]

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: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: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.

 

[Karl Heinz Buchegger]

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;
}
}

 

[Howard]

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

 

[David Hilsee]

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]

[...]

std::vector<int> numbersSeen( n + 1 );

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