## Saturday, April 22, 2017

### Given pairwise sum of n numbers, find the numbers - GeeksforGeeks

Given pairwise sum of n numbers, find the numbers - GeeksforGeeks
Pairwise sum of n (where n >= 3) numbers are given in a specified order, find the numbers. The order has pair sum of first and second, then first and third, first and fourth, … second and third, second and fourth, .. and so on. Consider an example: n = 4, let the numbers be {a, b, c, d}, their pairwise sum is given in the order arr[] = {a+b, a+c, a+d, b+c, b+d, c+d}.

```n = 3, {a+b, a+c, b+c}
We can find b-a = arr[2] - arr[1]
= (b+c) - (a+c)
We can find b = (arr[0] + (b-a))/2
= (a + b + (b - a))/2
= b
We can find a = arr[0] - b
= a

n = 4, {a+b, a+c, a+d, b+c, b+d, c+d}
We can find b-a = arr[3] - arr[1]
= (b+c) - (a+c)
We can find b = (arr[0] + (b-a)) / 2
= ((a+b) + (b-a)) / 2
a = arr[0] - b
= (a+b) - b
c = arr[1] - a
= (a+c) - a
d = arr[2] - a
= (a+d) - a

Observation :
b_minus_a = b - a = arr[n-1] - arr[1]
b = (arr[0] + b_minus_a)/2
a = (arr[0] - b)
c = arr[1] - a
d = arr[2] - a
..........

n = 5, {a+b, a+c, a+d, a+e, b+c,
b+d, b+e, c+d, c+e, d+e}

Then calculate b-a = arr[n-1] - arr[1]
= (b+c) - (a+c)
Then b = (arr[0] + (b-a)) / 2
= ((a+b) + (b-a)) / 2
a = arr[0] - b
= (a+b) - b
Then for i=1 to n-2,
remaining numbers are calculated as
arr[i] - a, like
c = arr[1] - a
= (a+c) - a
d = arr[2] - a
= (a+c) - a      and so on,
.
.
.
.
last number = arr[n-2] - a ```
`void` `findNumbers(``int` `arr[], ``int` `n)`
`{`
`    ``int` `num[n];`

`    ``// b-a is calculated here`
`    ``int` `b_minus_a = arr[n-1] - arr[1];`

`    ``// b is calculated here`
`    ``num[1] = (arr[0] + b_minus_a) / 2;`

`    ``// a is calculated here`
`    ``num[0] = arr[0] - num[1];`

`    ``// to calculate all the other numbers`
`    ``for` `(``int` `i=1; i<=(n-2); i++)`
`        ``num[i+1] = arr[i] - num[0];`

`    ``// display the numbers`
`    ``cout << ``"Numbers are: "``;`
`    ``for` `(``int` `i=0; i<n; i++)`
`        ``cout << num[i] << ``" "``;`
`}`