Construct an array from its pair-sum array - GeeksQuiz
A pair-sum array for an array is the array that contains sum of all pairs in ordered form. For example pair-sum array for arr[] = {6, 8, 3, 4} is {14, 9, 10, 11, 12, 7}.
In general, pair-sum array for arr[0..n-1] is {arr[0]+arr[1], arr[0]+arr[2], ……., arr[1]+arr[2], arr[1]+arr[3], ……., arr[2]+arr[3], arr[2]+arr[4], …., arr[n-2]+arr[n-1}.
"Given a pair-sum array, construct the original array."
Let the given array be “pair[]” and let there be n elements in original array. If we take a look at few examples, we can observe that arr[0] is half of pair[0] + pair[1] – pair[n-1]. Note that the value of pair[0] + pair[1] – pair[n-1] is (arr[0] + arr[1]) + (arr[0] + arr[2]) – (arr[1] + arr[2]).
Once we have evaluated arr[0], we can evaluate other elements by subtracting arr[0]. For example arr[1] can be evaluated by subtracting arr[0] from pair[1], arr[2] can be evaluated by subtracting arr[0] from pair[2].
Read full article from Construct an array from its pair-sum array - GeeksQuiz
A pair-sum array for an array is the array that contains sum of all pairs in ordered form. For example pair-sum array for arr[] = {6, 8, 3, 4} is {14, 9, 10, 11, 12, 7}.
In general, pair-sum array for arr[0..n-1] is {arr[0]+arr[1], arr[0]+arr[2], ……., arr[1]+arr[2], arr[1]+arr[3], ……., arr[2]+arr[3], arr[2]+arr[4], …., arr[n-2]+arr[n-1}.
"Given a pair-sum array, construct the original array."
Let the given array be “pair[]” and let there be n elements in original array. If we take a look at few examples, we can observe that arr[0] is half of pair[0] + pair[1] – pair[n-1]. Note that the value of pair[0] + pair[1] – pair[n-1] is (arr[0] + arr[1]) + (arr[0] + arr[2]) – (arr[1] + arr[2]).
Once we have evaluated arr[0], we can evaluate other elements by subtracting arr[0]. For example arr[1] can be evaluated by subtracting arr[0] from pair[1], arr[2] can be evaluated by subtracting arr[0] from pair[2].
void
constructArr(
int
arr[],
int
pair[],
int
n)
{
arr[0] = (pair[0]+pair[1]-pair[n-1]) / 2;
for
(
int
i=1; i<n; i++)
arr[i] = pair[i-1]-arr[0];
}
int
pair[] = {15, 13, 11, 10, 12, 10, 9, 8, 7, 5};
int
n = 5;
int
arr[n];
constructArr(arr, pair, n);