need help defining Constant memory requirement
Jani Yusef
jani at persian.com
Sun Sep 19 07:00:11 CEST 2004
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"
More information about the Python-list
mailing list