need help defining Constant memory requirement
heikowu at ceosg.de
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