need help defining Constant memory requirement

Jani Yusef jani at persian.com
Sun Sep 19 23:28:35 CEST 2004


Heiko Wundram <heikowu at ceosg.de> wrote in message news:<mailman.3507.1095603871.5135.python-list at python.org>...
> 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.

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.



More information about the Python-list mailing list