I saw this question in a programming interview blog.
If pairwise sums of
nnumbers 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.
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