algorithm - 如何解这个方程来解 "Finding duplicate in integer array"

Question

我在这里查看问题和讨论:Easy interview question got harder: given numbers 1..100, find the missing number(s)

其中一位用户使用以下等式提供了解决方案。 k1 + k2 = x

k1^2 + k2^2 = y

替换提供 (x-k2)^2 + k2^2 = y

我试图进一步求解这个方程，并提出一个 C 程序来解决查找重复项的问题。 尽管花了很多时间，但我无法解出这个方程来得到 k1 或 k2 的一侧。我总是以等式两边的 k1 或 k2 结尾。

感谢任何帮助。

Answer 1

展开方程式

(x - k2)^2 + k2^2 = y

得到

x^2 - 2xk2 + 2k2^2 = y

或

2k2^2 - 2xk2 + x^2 - y = 0

现在使用公式求解二次方程 az^2 + bz + c = 0 即 (-b +/- sqrt(b^2 - 4ac))/2a 。只有在我们的例子中 z=k2。所以

k2 = (2x +/- sqrt(4x^2 - 8(x^2 - y))) / 4

或

k2 = (x +/- sqrt(x^2 - 2(x^2 - y))) / 2

   = (x +/- sqrt(2y - x^2)) / 2

你可以把

k2 = (x + sqrt(2y - x^2)) / 2
k1 = (x - sqrt(2y - x^2)) / 2.