Home Original page

need help defining Constant memory requirement

Heiko Wundram heikowu at ceosg.de
Sun Sep 19 10:24:38 EDT 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)

Heiko.
More information about the Python-list mailing list