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