Home » Data Structure » Array Data Structure

Construct an array from its pair-sum array

C++ implementation to construct an array from its pair-sum array.
Submitted by Vikneshwar GK, on February 06, 2022

A pair-sum array is an array that contains the sum of all pairs, that can be formed from the original array, in an ordered form. For example, if the original array is {1, 2, 3, 4}, then the pair-sum array is {3, 4, 5, 5, 7}, where 3 is formed by 1+2, 4 is formed by 1+3, and so on.

Consider a pair-sum array and the size of the original array that is n. The task at hand is to find the original array using the given data.

Example

Input:
pair[] = {12, 8, 7, 10, 9, 5}
n = 4

Output:
array[] = {5, 7, 3, 2}

Explanation:
array[0] = (12+8-10)/2 = 5
array[1] = 12 - 5 = 7
array[2] = 8 - 5 = 3
array[3] = 7 - 5 = 2

Solution:

On observing the problem statement and examples, we identify a pattern that is adding pair[0] and pair[1], subtracting pair[n-1] from it, and finally dividing it by 2 will give us array[0], that is, the first element in the original array. In other words, we can say that array[0] = (pair[0]+pair[1]-pair[n-1])/2.

After obtaining array[0], we can identify other elements by the following pattern.

array[1] = pair[0] - array[0]
array[2] = pair[1] - array[0]
.
.
.
array[n] = pair[n-1] - array[0]

C++ Implementation

#include <bits/stdc++.h>
using namespace std;

// function to find original array
// from pair-sum array
void pairSumArray(int array[], int pair[], int length)
{
    array[0] = (pair[0] + pair[1] - pair[length - 1]) / 2;
    for (int i = 1; i < length; i++)
        array[i] = pair[i - 1] - array[0];
}

//Function to print the array
void printArray(int array[], int length)
{
    for (int i = 0; i < length; i++)
        cout << array[i] << " ";
    cout << endl;
}

// Main function
int main()
{
    int pair[100], N, array[100], length;
    
    cout << "Enter Number of elements for pair-sum array: ";
    cin >> N;

    for (int i = 0; i < N; i++) {
        cout << "Enter element " << i + 1 << ":";
        cin >> pair[i];
    }
    cout << "Enter Number of elements for original array: ";
    cin >> length;

    pairSumArray(array, pair, length);

    cout << "Original array:" << endl;
    printArray(array, length);

    return 0;
}

Output:

Enter Number of elements for pair-sum array: 5
Enter element 1:3
Enter element 2:4
Enter element 3:5
Enter element 4:5
Enter element 5:7
Enter Number of elements for original array: 4
Original array:
1 2 3 4 

Time Complexity: O(n)