need help defining Constant memory requirement

Heiko Wundram heikowu at
Sun Sep 19 16:24:38 CEST 2004

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)


More information about the Python-list mailing list