0
$\begingroup$

I'm currently studying the time complexity of the solution provided by my teacher to this problem, and I can't understand the logic:

Let A be an unordered array of positive natural numbers. Write an algorithm that checks if it's possible to divide A into pairs (subsets of two elements) of equal sum.

Example [1 7 4 2 4 0 8 6] is composed of 1+7, 4+4, 2+6 etc all of which give 8.

Now, the solution works like this: it sorts the array, and then checks if the sum of $A[i]$ and $A[length-i]$ (indexes start at 1) always give the same value.

Example: [0 1 2 4 4 6 7 8] is the above array after reordering. Checks 0+8=8, then 1+7=8, then 2+6=8 etc.

So the algorithm returns True, since every $(n,n-i)$ pair in the array always gives the same sum.

My problem with this is that I can't understand why positioning the elements with this symmetry would give an equal sum everytime.

Why taking the $i$ and $n-i$ elements would give the same sum?

$\endgroup$
  • 2
    $\begingroup$ Well it wouldn't necessarily give an equal sum every time. This can easily be seen by replacing, the 8 with 10. The reason your example seems symmetric is because you are adding 1 to every element on your LHS and subtracting 1 from every element on your RHS. $\endgroup$ – Gary Andrews30 May 19 '18 at 13:12
1
$\begingroup$

For simplicity, let's pretend there are no duplicates in your array. The answer generalizes easily to arrays containing duplicates.

If the array can be divided into pairs of equal sum, then the lowest number (on place $0$ in the sorted array) and the highest number (on place $n$ in the sorted array) has to be a pair. We can do a proof be contradiction by assuming that the lowest number ($x_0$) and the highest number ($x_n$) is not a pair. As all numbers in the array needs to be in a pair, this implies that $x_0$ is in a pair with an other number $x_j$ and likewise that $x_n$ is in a pair with $x_k$. As $x_n$ is the highest number, it must be that $x_j \lt x_n$ and therefore, in order for $x_o + x_j$ to be equal to $x_k + x_n$ it must be that $x_k \lt x_0$ but this goes against our assumption that $x_0$ is the lowest number.

Having proved that $x_0$ and $x_n$ is a pair, the same proof now goes for $x_1$ and $x_{n-1}$ and recursively for the whole array.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ Oops, didn't see that another totally adequate answer had been written while I made mine. $\endgroup$ – AstridNeu May 20 '18 at 9:35
  • $\begingroup$ Thank you for the proof, it was very useful for understanding. Another quick question: is this a "trivial" property? (meaning you can easily see this without explaining) $\endgroup$ – riciloma May 20 '18 at 14:48
  • $\begingroup$ I would not call it trivial, although the proof is quite simple. $\endgroup$ – AstridNeu May 20 '18 at 14:52
1
$\begingroup$

You sort the array in increasing order.

If you pair an element equal to the largest element with any element that is larger than the smallest element, then pairing the smallest element with any other element will give a smaller sum, and therefore a different sum.

Therefore, to find pairs that all have the same sum, you must pair an element equal to the largest with an element equal to the smallest, and then repeat for the remaining elements. This will give you pairs with equal sums if it is possible. If not possible, then of course you won't get equal sums.

| cite | improve this answer | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.