need help defining Constant memory requirement
tim.peters at gmail.com
Mon Sep 20 22:11:50 CEST 2004
>> Got it!! Thanks for your help.
>> Here is my revised and working code
> > s1=0
>> for a in i:
>> return (sum1-sum0)%len(i)
>> I think my main malfunction was with thinking that this was mor
>> ecomplex tna it was. By refocusing on the simple problem statement as
>> suggested the solution came easier. Thanks again.
> Well, actually, as Tim Peters already said, the function really isn't O(1) in
> space requirement, because len(i) and sum(i) grow with O(log(n))... But okay,
> probably your instructor just overlooked this...
FYI, I had in mind a different (albeit related) solution, which
doesn't require more bits in "a word" than are needed to hold n-1;
assuming the integer n-1 takes O(1) space, then so does this approach:
result = 0
for i, x in enumerate(iterable):
result ^= i ^ x
>>> N = 100000
>>> import random
>>> ints = range(1, N)
>>> dup = random.choice(ints)
Of course holding n**2 takes O(1) space too, but in most languages
requires faking double-precision integer arithmetic. Basing the
reduction instead on that a collection of ints xor'ed with itself
yields 0 allows getting away with single-precision operations.
More information about the Python-list