need help defining Constant memory requirement

[Tim Peters]

[Tim Peters]
>> def finddup(iterable):
>>     result = 0
>>     for i, x in enumerate(iterable):
>>         result ^= i ^ x
>>     return result

[Heiko Wundram]
> Erm... Shouldn't this function be:

No.  Try it!

> 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... ;)

I think you misunderstand what enumerate does.  enumerate() starts at
0, not at 1.  So enumerate generates 0, 1, .., n-1 here, where n ==
len(it).  The 0 has no effect, and the rest cancel out 1 thru n-1 from
the sequence.  All that remains then is the duplicate.in the sequence.