need help defining Constant memory requirement
Tim Peters
tim.peters at gmail.com
Tue Sep 21 15:20:08 CEST 2004
[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.
More information about the Python-list
mailing list