>>> from random import shuffle
>>> def test(n, missing, extra):
... t = [i if i != missing else extra for i in range(1, n + 1)]
... shuffle(t)
... return t
...
>>> def solve(list):
... diff, diffsq, n = 0, 0, 1
... for i in list:
... diff += i - n
... diffsq += i*i - n*n
... n += 1
... sum = diffsq / diff
... return {'extra': (sum + diff)/2, 'missing': (sum - diff)/2}
...
>>> solve(test(7633507, missing=3518688, extra=4057456))
{'missing': 3518688L, 'extra': 4057456L} >>> from math import exp, log
>>> ref = [i for i in range(1, 500000)]
>>> test = [i if i != 7922 else 59148 for i in ref]
>>> s = sum(test) - sum(ref)
>>> r = exp(sum(map(log, test)) - sum(map(log, ref)))
>>> b = s/(r - 1); b
7921.999994157095
>>> (int(round(b)), s + int(round(b)))
(7922, 59148)
Python of course has bignums, so we can also calculate these products directly, but that gets to be a very large calculation; you don't want to be storing N! for N ~= 2^64 if at all possible.
If we know that these numbers are bounded by 2^n (e.g. they're all longs) then we might be able to do this product modulo some larger base, perhaps even 2^n, with the assurance that when we do the division all of that crap will cancel; I don't know and haven't tried it.
2°: s sum, p product, solve the linear system {n(n+1)/2-x+y=s; n!y = px}
1: n(n+1)/2 - x + y = s
Product of first n natural numbers is represented as: n! The product of the numbers in array is p.
2: p x / y = n!
(multiply by x - add missing number to product and divide by y - remove duplicated number from product).