Pairwise Sum

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
4 5 7 10 12 13

o/p:
1 3 4 9

Here's the solution courtsey TopCoder.com

We will build A up from smallest element to largest. Suppose A and B are integer lists such that B gives the pairwise sums for A, where A[0] < A[1] < A[2] < ... and B[0] <= B[1] <= B[2] <= ... . Given B, we wish to find A. Suppose that we already know A[0]. Then, since P[0] is the smallest element in B, it can only arise as A[0] + A[1]. Similarly, P[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.

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].

Similarly, if we know A[0], A[1], A[2], and A[3], we can remove A{i}+A[j], 0 <= i < j <= 3, from B. The next smallest element of B will be A[0]+A[4], which allows us to compute A[4]. Repeating in this way, we can find all of A without ever backtracking.

Thus, once we know A[0], we can compute the rest of A. For this problem, we can now simply try every possibility for A[0]. We are given A contains only distinct non-negative integers, and A[1] > A[0], so A[0] must be an integer between 0 and B[0]/2 - 1 inclusive.

So whatever is the maximum value of B[0], we will have to try B[0]/2 possibilities for A[0].