# C++ Programming – Construct an array from its pair-sum array

C++ Programming - Construct an array from its pair-sum array - Algorithm - A pair-sum array for an array is array that contains sum of all pairs in ordered

Given a pair-sum array and size of the original array (n), construct the original array.

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+arr, arr+arr, ……., arr+arr, arr+arr, ……., arr+arr, arr+arr, …., 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 is half of pair + pair – pair[n-1]. Note that the value of pair + pair – pair[n-1] is (arr + arr) + (arr + arr) – (arr + arr).
Once we have evaluated arr, we can evaluate other elements by subtracting arr. For example arr can be evaluated by subtracting arr from pair, arr can be evaluated by subtracting arr from pair.

Following are C++ and Java implementations of the above idea.

C++ Program
``````#include <iostream>
using namespace std;

// Fills element in arr[] from its pair sum array pair[].
// n is size of arr[]
void constructArr(int arr[], int pair[], int n)
{
arr = (pair+pair-pair[n-1]) / 2;
for (int i=1; i<n; i++)
arr[i] = pair[i-1]-arr;
}

// Driver program to test above function
int main()
{
int pair[] = {15, 13, 11, 10, 12, 10, 9, 8, 7, 5};
int n = 5;
int arr[n];
constructArr(arr, pair, n);
for (int i = 0; i < n; i++)
cout << arr[i] << " ";
return 0;
}``````

Output:

` 8 7 5 3 2`

Time complexity of constructArr() is O(n) where n is number of elements in arr[].

READ  C Programming - check for pair in A[] with sum as x #### Wikitechy Editor

Wikitechy Founder, Author, International Speaker, and Job Consultant. My role as the CEO of Wikitechy, I help businesses build their next generation digital platforms and help with their product innovation and growth strategy. I'm a frequent speaker at tech conferences and events.

X