An easy way to do the second is to consider the sum and the sum of squares. This gets you a-b and a^2-b^2. Recall that the latter is (a-b)(a+b) and the answer follows immediately.

That is probably the classiest way I've seen yet to do the second problem. Since I gave Python code above, here it is for your version:

    >>> 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}

At the very least, you could do it with logs like so:

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

The use of logs is really just a convenience for finding product(test) and product(ref), so that we have both a - b (from the sums) and a/b (from the ratio of the products).

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.

1°: s is the sum of the numbers in the array, x = n(n+1)/2-s

2°: s sum, p product, solve the linear system {n(n+1)/2-x+y=s; n!y = px}

The second solution works in linear time only if one assumes that multiplication is a constant time operation. But is it really? If you look at how a processor does multiplication it becomes clear it is a O(log n) operation where n is one of the numbers being multiplied. Thus, the second solution is probably a O(nlogn) solution.

It also requires one to assume n! can be computed. Factorials get huge very quickly.

Sorry, can you expand on what you meant by that?

Sum of first n natural numbers is n(n+1)/2. The sum of the array, represented by s, is n(n+1)/2 - x + y (subtract x - the missing number and add y - the duplicated number) gives:

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

If a is duplicated and b missing, computing the sum and the product of all the numbers can give you a-b and a/b, from which you can deduce a and b.