 |
Bill Godfrey wrote:
> 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?
It may be allowed, but it is not necessary ...
> Is there an answer where the original array is const? My instinct
tells me
> that's impossible, but I stand awaiting surprise.
It is certainly possible to solve under the given conditions (O(n) in
time and O(1) in mem) using a const object for the initial array. You
can identify the "missing" values using two passes through the array ..
I don't know if it can be done using fewer.
Hint: The fact that the initial integers are consecutive is the key ..
>
> Bill, foot hunting.
>
> --
> http://billpg.me.uk/
> usenet(at)billpg(dot)me(dot)uk
|
|
