|
|
 | | From: | Alf P. Steinbach | | Subject: | Re: array Puzzle | | Date: | Thu, 20 Jan 2005 02:07:55 GMT |
|
|
 | * 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?
|
|
| | From: | Bill Godfrey | | Subject: | Re: array Puzzle | | Date: | 21 Jan 2005 16:56:34 GMT |
|
|
| alfps@start.no (Alf P. Steinbach) wrote:
> 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.
I think I have an answer that both conforms to O(1) extra memory and O(n)
time. However, it requires modification of the original array. Is that
allowed?
Is there an answer where the original array is const? My instinct tells me
that's impossible, but I stand awaiting surprise.
Bill, foot hunting.
--
http://billpg.me.uk/
usenet(at)billpg(dot)me(dot)uk
|
|
|
