Pairwise sum of n numbers in non increasing order

Question

I saw this question in a programming interview blog.

If pairwise sums of n numbers are given in non-decreasing order identify the individual numbers. If the sum is corrupted print -1.

Example:

i/p: 4 5 7 10 12 13 

o/p: 1 3 4 9

A hint would suffice.

Answer 1

Let B be the list of pairwise sums, with B[0] <= B[1] <= ... <= B[m-1] and let A be the original list of numbers that we're trying to find, with A[0] < A[1] < ... < A[n-1], where m = n(n-1)/2.

Given A[0], compute A in polynomial time

Build A up from smallest element to largest. Suppose that we already know A[0]. Then, since B[0] is the smallest element in B, it can only arise as A[0] + A[1]. Similarly, B[1] must equal A[0] + A[2]. Therefore, if we know A[0], we can compute A[1] and A[2].

After that, however, this pattern breaks down. B[2] could either be A[0] + A[3] or A[1] + A[2] and without prior knowledge, we cannot know which one it is. However, if we know A[0], we can compute A[1] and A[2] as described above, and then remove A[1] + A[2] from B. The next smallest element is then guaranteed to be A[0] + A[3], which allows us to find A[3]. Continuing like this, we can find all of A without ever backtracking. The algorithm looks something like this:

for i from 1 to n-1 {
    // REMOVE SEEN SUMS FROM B
    for j from 0 to i-2 {
        remove A[j]+A[i-1] from B
    }
    // SOLVE FOR NEXT TERM
    A[i] = B[0] - A[0]
}
return A

Here's how this works from your example where B = [4,5,7,10,12,13] if we know A[0]=1:

start
    B = [4,5,7,10,12,13]
    A[0] = 1

i=1: 
    B = [4,5,7,10,12,13]
    A[1] = 4-1 = 3

i=2:
    Remove 1+3 from B
    B = [5,7,10,12,13]
    A[2] = 5-1 = 4

i=3:
    Remove 1+4 and 3+4 from B
    B = [10,12,13]
    A[3] = 10-1 = 9

end
    Remove 1+9 and 3+9 and 4+9 from B
    B = []
    A = [1,3,4,9]

So it all comes down to knowing A[0], from which we can compute the rest of A.

Compute A[0] in polynomial time

We can now simply try every possibility for A[0]. Since we know B[0] = A[0] + A[1], we know A[0] must be an integer between 0 and B[0]/2 - 1. We also know that

B[0] = A[0] + A[1]
B[1] = A[0] + A[2]

Moreover, there is some index i with 2 <= i <= n-1 such that

B[i] = A[1] + A[2]

Why? Because the only entries potentially smaller than A[1]+A[2] are of the form A[0] + A[j], and there are at most n-1 such expressions. Therefore we also know that

A[0] = (B[0]+B[1] - B[i])/2

for some 2 <= i <= n-1. This, together with the fact that A[0] lies between 0 and B[0]/2-1 gives only a few possibilities for A[0] to test.

For the example, there are two possibilities for A[0]: 0 or 1. If we try the algorithm with A[0]=0, here's what happens:

start
    B = [4,5,7,10,12,13]
    A[0] = 0

i=1: 
    B = [4,5,7,10,12,13]
    A[1] = 4-0 = 4

i=2:
    Remove 0+4 from B
    B = [5,7,10,12,13]
    A[2] = 5-0 = 5

i=3:
    Remove 0+5 and 4+5 from B
    B = !!! PROBLEM, THERE IS NO 9 IN B!

end

Answer 2

Some hints:

• The size of the input is N*(N-1)/2, so you can deduce the size of the output (i.e. 6 elements in the input correspond to 4 elements in the output)

• The sum of the input is the sum of the output divided by N - 1 (i.e. 1+3+4+9 = (4+5+7+10+12+13) / (4-1))

• The lowest input and highest inputs are the sum of the two lowest and two highest outputs respectively (i.e. 4 = 1 + 3 and 13 = 4 + 9)

• The next lowest input (5) is differs by only one addend from the first (1), so you can compute one of the addends by taking the difference (5-1).

Answer 3

Ferdinand Beyer was on the right track, I think, before he deleted his answer. To repeat part of his approach: you have four unknowns, a, b, c, and d with a ≤ b ≤ c ≤ d. From this, one can form a partial ordering of all the sums:

a + b ≤ a + c
a + b ≤ a + d
a + c ≤ b + c
a + d ≤ b + d
a + d ≤ c + d
b + c ≤ b + d
b + d ≤ c + d

If this were a total order, then one would know each of the six values a + b, a + c, a + d, b + c, b + d, and c + d. One could then follow Ferdinand's original plan and easily solve the simultaneous equations.

Unfortunately, there is the pair (a + d, b + c), which can be ordered either way. But this is easy enough to handle: assume that a + d < b + c (the input values are all distinct, so one need not worry about using ≤) and try to solve the simultaneous equations. Then assume b + c < a + d and repeat. If both sets of equations have a solution, then the original problem has two answers. If neither set has a solution, then the output should be -1. Otherwise, you have your (unique) solution.