need help defining Constant memory requirement

J

Jani Yusef

I have a HW problem stated as shown at the top of the solution. The
thing is is that I am not 100% sure wtf constant memory means. Well, I
think I do but I am confused. Does my solution use contant memory in
terms of the length of the list i? If so why not and how could I
change it to be so? I am sure the solution is O(n) since the list must
only iterated once and the dictionary is O(1), correct?
Thanks for the help!!


#You are given a sequence S of n numbers whose values range from 1 to
n-1.
#One of these numbers repeats itself once in the sequence.
#(Examples: {1 2 3 4 5 6 3}, {4 2 1 2 3 6 5}).
#Write a function that finds this repeating number using a constant
#amount of memory and linear time.
import sys
i=[1,3,4,5,3]
tally={}
for a in i:
if tally.has_key(a):
print "repeated number is "+str(a)
sys.exit(0)
else:
tally[a]=1
print "no repeat found"
 
A

Andrew Koenig

Jani Yusef said:
I have a HW problem stated as shown at the top of the solution. The
thing is is that I am not 100% sure wtf constant memory means. Well, I
think I do but I am confused. Does my solution use contant memory in
terms of the length of the list i? If so why not and how could I
change it to be so? I am sure the solution is O(n) since the list must
only iterated once and the dictionary is O(1), correct?
Thanks for the help!!

Constant memory means the same as O(1) memory -- in other words, that it is
possible to place an upper bound on the total amount of memory used (aside
from the input) regardless of how large the input is.
#You are given a sequence S of n numbers whose values range from 1 to
n-1.
#One of these numbers repeats itself once in the sequence.
#(Examples: {1 2 3 4 5 6 3}, {4 2 1 2 3 6 5}).
#Write a function that finds this repeating number using a constant
#amount of memory and linear time.
import sys
i=[1,3,4,5,3]
tally={}
for a in i:
if tally.has_key(a):
print "repeated number is "+str(a)
sys.exit(0)
else:
tally[a]=1
print "no repeat found"

This program doesn't use constant memory, because tally might conceivably
have as many as n-1 elements, where n is the number of elements in the
input. Therefore the total amount of space needed is O(n), not O(1).

One question you might ask: Is the entire input sequence available at once?
Is it permissible to modify its elements?
 
T

Tim Peters

[Jani Yusef]
I have a HW problem stated as shown at the top of the solution. The
thing is is that I am not 100% sure wtf constant memory means.

It means the amount of memory needed is independent of input size.
Well, I think I do but I am confused. Does my solution use contant
memory in terms of the length of the list i?

The "constant" in "constant memory" means you don't get to use more
memory for larger inputs, so "in terms of the length of the list"
isn't valid. Your solution requires creating a dict with n-1
elements, and so requires O(n) memory, not constant memory.
If so why not

Because the amount of memory needed increases as the input size increases.
and how could I change it to be so?

With the approach you've taken, you cannot. You need a different
approach. Since finding such an approach is apparently the point of
the exercise, I'm not going to spell that out. As a hint, you need to
*exploit* all the information you've been given about the inputs.
Note that the solution you have works for any input sequence, whether
or not the values range from 1 to n-1, and whether there are 0, 1, 2,
...., or millions of duplicates. You only *need* a solution that works
in the case of an input sequence containing a permutation of 1 .. n-1,
plus exactly one duplicate.
I am sure the solution is O(n) since the list must only iterated once and the
dictionary is O(1), correct?

Yes, it's O(n) (expected) in time, but also O(n) in space.
Thanks for the help!!

#You are given a sequence S of n numbers whose values range from 1 to n-1.
#One of these numbers repeats itself once in the sequence.
#(Examples: {1 2 3 4 5 6 3}, {4 2 1 2 3 6 5}).
#Write a function that finds this repeating number using a constant
#amount of memory and linear time.
import sys
i=[1,3,4,5,3]

Note that this example doesn't meet the input requirements -- you're
not required to get the right answer for this one. [1, 3, 4, 2, 3]
meets the requirements, though.
tally={}
for a in i:
if tally.has_key(a):
print "repeated number is "+str(a)
sys.exit(0)
else:
tally[a]=1
print "no repeat found"

You're not required to get the right answer in the case of no duplicates either.

FYI, it is possible to solve the problem with a constant number of
memory locations, assuming a memory location is big enough to hold one
integer. That isn't *really* constant-memory either, though, because
holding one integer requires a number of bits proportional to log(n),
which also increases as the input size increases; I suspect your
instructor is overlooking that detail.
 
H

Heiko Wundram

Am Sonntag, 19. September 2004 07:00 schrieben Sie:
I am sure the solution is O(n) since the list must
only iterated once and the dictionary is O(1), correct?
Thanks for the help!!

In case you haven't found a solution yet, think about the properties of the
sum of the numbers of the sequence which is n*(n-1)/2 + x with 0 < x < n,
where finding out why this equation holds and what x is is up to you.

(n being defined as in your example, a sequence having n elements with the
elements in 1..n-1 and only one repeated)

Heiko.
 
J

Jani Yusef

Heiko Wundram said:
Am Sonntag, 19. September 2004 07:00 schrieben Sie:

In case you haven't found a solution yet, think about the properties of the
sum of the numbers of the sequence which is n*(n-1)/2 + x with 0 < x < n,
where finding out why this equation holds and what x is is up to you.

(n being defined as in your example, a sequence having n elements with the
elements in 1..n-1 and only one repeated)

Heiko.

Got it!! Thanks for your help.
Here is my revised and working code
i=[1,2,3,4,5,6,3]
s0=len(i)*(len(i)+1)/2
s1=0
for a in i:
sum1+=a
return (sum1-sum0)%len(i)
I think my main malfunction was with thinking that this was mor
ecomplex tna it was. By refocusing on the simple problem statement as
suggested the solution came easier. Thanks again.
 
H

Heiko Wundram

Am Sonntag, 19. September 2004 23:28 schrieb Jani Yusef:
Got it!! Thanks for your help.
Here is my revised and working code
i=[1,2,3,4,5,6,3]
s0=len(i)*(len(i)+1)/2
s1=0
for a in i:
sum1+=a
return (sum1-sum0)%len(i)
I think my main malfunction was with thinking that this was mor
ecomplex tna it was. By refocusing on the simple problem statement as
suggested the solution came easier. Thanks again.

Well, actually, as Tim Peters already said, the function really isn't O(1) in
space requirement, because len(i) and sum(i) grow with O(log(n))... But okay,
probably your instructor just overlooked this...

Heiko.
 
T

Tim Peters

[Jani Yusef]
Got it!! Thanks for your help.
Here is my revised and working code
i=[1,2,3,4,5,6,3]
s0=len(i)*(len(i)+1)/2
s1=0
for a in i:
sum1+=a
return (sum1-sum0)%len(i)
I think my main malfunction was with thinking that this was mor
ecomplex tna it was. By refocusing on the simple problem statement as
suggested the solution came easier. Thanks again.

[Heiko Wundram]
Well, actually, as Tim Peters already said, the function really isn't O(1) in
space requirement, because len(i) and sum(i) grow with O(log(n))... But okay,
probably your instructor just overlooked this...

FYI, I had in mind a different (albeit related) solution, which
doesn't require more bits in "a word" than are needed to hold n-1;
assuming the integer n-1 takes O(1) space, then so does this approach:

def finddup(iterable):
result = 0
for i, x in enumerate(iterable):
result ^= i ^ x
return result

Then, e.g.,

Of course holding n**2 takes O(1) space too, but in most languages
requires faking double-precision integer arithmetic. Basing the
reduction instead on that a collection of ints xor'ed with itself
yields 0 allows getting away with single-precision operations.
 
H

Heiko Wundram

Am Montag, 20. September 2004 22:11 schrieb Tim Peters:
def finddup(iterable):
result = 0
for i, x in enumerate(iterable):
result ^= i ^ x
return result

Erm... Shouldn't this function be:

def finddup(it):
result = 0
for i, x in enumerate(it):
result ^= i ^ x
return result ^ i

Because in ( 1 ^ 1 ) ^ ( 2 ^ 2 ) ... ^ ( (n-1) ^ (n-1) ) ^ ( x ^ n ) all terms
zero out except the last one. So, basically what you get is x ^ n, and x ^
( n ^ n ) = x...

Guess that was just a typo... ;)

Heiko.
 
T

Tim Peters

[Tim Peters]
[Heiko Wundram]
Erm... Shouldn't this function be:

No. Try it!
def finddup(it):
result = 0
for i, x in enumerate(it):
result ^= i ^ x
return result ^ i

Because in ( 1 ^ 1 ) ^ ( 2 ^ 2 ) ... ^ ( (n-1) ^ (n-1) ) ^ ( x ^ n ) all terms
zero out except the last one. So, basically what you get is x ^ n, and x ^
( n ^ n ) = x...

Guess that was just a typo... ;)

I think you misunderstand what enumerate does. enumerate() starts at
0, not at 1. So enumerate generates 0, 1, .., n-1 here, where n ==
len(it). The 0 has no effect, and the rest cancel out 1 thru n-1 from
the sequence. All that remains then is the duplicate.in the sequence.
 

Ask a Question

Want to reply to this thread or ask your own question?

You'll need to choose a username for the site, which only take a couple of moments. After that, you can post your question and our members will help you out.

Ask a Question

Members online

No members online now.

Forum statistics

Threads
473,744
Messages
2,569,483
Members
44,903
Latest member
orderPeak8CBDGummies

Latest Threads

Top