|
|
 | | From: | dtmoore | | Subject: | Re: array Puzzle | | Date: | 22 Jan 2005 17:59:05 -0800 |
|
|
 |
Alf P. Steinbach wrote:
> * 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?
[Snip}
> 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.
>
Ok, I can see how to solve the puzzle with an algorithm that is O(n) in
time and O(1) in memory, but only when two values are removed. Is
there to solve it when more than two values are zero'd out and still
use O(1) memory? (of course it is still trivial if you are allowed
O(n) memory 8*).
Dave Moore
|
|
| | From: | Alf P. Steinbach | | Subject: | Re: array Puzzle | | Date: | Sun, 23 Jan 2005 06:16:19 GMT |
|
|
| * dtmoore:
>
> Alf P. Steinbach wrote:
> > * 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?
>
> [Snip}
>
> > 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.
> >
>
> Ok, I can see how to solve the puzzle with an algorithm that is O(n) in
> time and O(1) in memory, but only when two values are removed. Is
> there to solve it when more than two values are zero'd out and still
> use O(1) memory?
Well I don't know.
I assume your solution involves a root?
If so, I don't think that generalizes very well (it seems to go in the
direction of the knapsack problem), but perhaps some mathematical mind
here could shed more light on that issue.
> (of course it is still trivial if you are allowed
> O(n) memory 8*).
Yep.
--
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?
|
|
|
