need help defining Constant memory requirement

Heiko Wundram heikowu at ceosg.de
Tue Sep 21 13:07:03 CEST 2004


Am Montag, 20. September 2004 22:11 schrieb Tim Peters:
> def finddup(iterable):
>     result = 0
>     for i, x in enumerate(iterable):
>         result ^= i ^ x
>     return result

Erm... Shouldn't this function be:

def finddup(it):
 result = 0
 for i, x in enumerate(it):
  result ^= i ^ x
 return result ^ i

Because in ( 1 ^ 1 ) ^ ( 2 ^ 2 ) ... ^ ( (n-1) ^ (n-1) ) ^ ( x ^ n ) all terms 
zero out except the last one. So, basically what you get is x ^ n, and x ^ 
( n ^ n ) = x...

Guess that was just a typo... ;)

Heiko.



More information about the Python-list mailing list