Yes -- thank you -- I have admitted in an earlier post that I posted
this variant in error. This variant has a very interesting solution,
however -- it is worth a look.
On Aug 26, 10:57 am, "[EMAIL PROTECTED]" <[EMAIL PROTECTED]> wrote:
> In your example, I noticed that all values are positive
nothing more to say... Thanks for the discussion.
On Aug 25, 2:53 pm, L7 <[EMAIL PROTECTED]> wrote:
> On Aug 25, 2:00 pm, wbspresslyjr <[EMAIL PROTECTED]> wrote:
>
> > You are mixing up implementation with theory here. The study of
>
> I would argue that neither of
solution
have this character? No. The size of your hash table changes. It is
not constant.
Perhaps you should heed the words of Dijkstra: "Computer science is no
more about computers than astronomy is about telescopes."
On Aug 25, 1:44 pm, wbspresslyjr <[EMAIL PROTECTED]>
"Always (notice my stipulation of 32 bit). However, regardless of the
size of an integer (in bits) there is _always_ a fixed number of bits
that can represent it in the manner I explained. "
Ther is no 32 bit requirement. When you are talking asymptotically, as
n grows infinitely large, there is
I am not sure that this is exactly the element uniqueness problem,
however -- does it matter in this problem statement that you are told
that there is a repetition, and that the goal is to find it? I am not
sure if that changes the problem or not...
I agree with you though, that there is no solut
it to (like the element uniqueness bound) --
unfortunately, the common bounds are not usually expressed in terms of
space complexity.
On Aug 24, 11:19 pm, L7 <[EMAIL PROTECTED]> wrote:
> On Aug 24, 10:19 pm, wbspresslyjr <[EMAIL PROTECTED]> wrote:
>
> > On Aug 21, 10:13
:19 pm, L7 <[EMAIL PROTECTED]> wrote:
> On Aug 24, 10:19 pm, wbspresslyjr <[EMAIL PROTECTED]> wrote:
>
> > On Aug 21, 10:13 pm, L7 <[EMAIL PROTECTED]> wrote:
>
> > > Sorry. I wrote too quickly. The amount you need is not determined by
> > > log, but by div
On Aug 21, 10:13 pm, L7 <[EMAIL PROTECTED]> wrote:
> Sorry. I wrote too quickly. The amount you need is not determined by
> log, but by division.
> For the sake of argument, say you could hold the value 0 - 255. This
> means we are dealing with 8-bit storage, but it makes the example
> easier. Yo
Oops -- sorry, I have been working on that problem lately... I guess I
didn't see that the problem you were working on was different --
Cheers,
W
On Aug 24, 5:46 pm, L7 <[EMAIL PROTECTED]> wrote:
> On Aug 24, 1:00 am, wbspresslyjr <[EMAIL PROTECTED]> wrote:
>
> > I
adding the numbers together is not constant space! that is logarithmic
space! As in log base 2 of N bits to represent the number... Thus, as
n grows large, your storage to hold the sum of the numbers is growing
logarithmically in the number of bits per element... Not to mention
that if the number
Here is the solution in PERL (this takes an Integer arg for the size
of the list of numbers, and outputs the list, the walks through the
lists, and the single repeating element) :
#!/usr/bin/perl
# setup problem -- this will embed the numbers 1...(N-1) into cells
1...N with one duplicate
# first
Aha! here is the other part:
http://en.wikipedia.org/wiki/Floyd's_cycle-finding_algorithm
On Aug 24, 2:11 am, wbspresslyjr <[EMAIL PROTECTED]> wrote:
> Oops -- for approach 1. down here, I meant to say that the hash table
> breaks the constant space requirement... I gue
Oops -- for approach 1. down here, I meant to say that the hash table
breaks the constant space requirement... I guess I got ahead of
myself :) (this also applies to sets, and about any other data
structure in general)...
On Aug 24, 1:00 am, wbspresslyjr <[EMAIL PROTECTED]> wrote:
> I
I've heard this problem stated as such: assume you have an array of N
numbers, each ranging on the interval [1,N-1], only one of these
elements repeating in Read-Only memory. You only have O(1) (constant)
"scratch" space to work with, and you need the algorithm to run in
O(n) time.
There were man
14 matches
Mail list logo
