3 ms·

A quick Google will find you the answer to the first question. The second just requires an additional equation, where people are suggesting powers in finite gro

A quick Google will find you the answer to the first question. The second just requires an additional equation, where people are suggesting powers in finite groups. This seems rather complex. Can we not reach the same constraints by only summing the even numbers, for instance?

Feanim 15y ago
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}
- alexchamberlain 15y ago
  Sorry, can you expand on what you meant by that?
  - gsa 15y ago
    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).
  - emillon 15y ago
    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.
- hristov 15y ago
  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.
  - alexchamberlain 15y ago
    It also requires one to assume n! can be computed. Factorials get huge very quickly.
drostie 15y ago
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.
nabb 15y ago
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.
- drostie 15y ago
  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}

Feanim 15y ago

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}

alexchamberlain 15y ago
Sorry, can you expand on what you meant by that?
- gsa 15y ago
  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).
- emillon 15y ago
  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.
hristov 15y ago
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.
- alexchamberlain 15y ago
  It also requires one to assume n! can be computed. Factorials get huge very quickly.

drostie 15y ago

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.

nabb 15y ago

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.

drostie 15y ago
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}