need help defining Constant memory requirement

[Tim Peters]

[Jani Yusef]
>> Got it!! Thanks for your help.
>> Here is my revised and working code
>>             i=[1,2,3,4,5,6,3]
>>             s0=len(i)*(len(i)+1)/2
> >             s1=0
>>             for a in i:
>>                 sum1+=a
>>             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.
 
[Heiko Wundram]
> 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:

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

Then, e.g.,

>>> N = 100000
>>> import random
>>> ints = range(1, N)
>>> dup = random.choice(ints)
>>> dup
43816
>>> ints.append(dup)
>>> random.shuffle(ints)
>>> finddup(ints)
43816
>>>

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.