7 ms·
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}
by Feanim 14y 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 14y agoSorry, can you expand on what you meant by that?
- gsa 14y agoSum 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 14y agoIf 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 14y agoThe 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 14y agoIt also requires one to assume n! can be computed. Factorials get huge very quickly.