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[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.”
We strongly recommend to minimize your browser and try this yourself.
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[0], arr[2] can be evaluated by subtracting arr[0] from pair[1].
Following is the implementation of the above idea.
C++
#include <bits/stdc++.h>
using namespace std;
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 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;
}
|
Java
import java.io.*;
class PairSum {
static 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];
}
public static void main(String[] args)
{
int pair[] = {15, 13, 11, 10, 12, 10, 9, 8, 7, 5};
int n = 5;
int[] arr = new int[n];
constructArr(arr, pair, n);
for (int i = 0; i < n; i++)
System.out.print(arr[i]+" ");
}
}
|
Python3
def constructArr(arr,pair,n):
arr [0] = (pair[0]+pair[1]-pair[n-1])//2
for i in range(1,n):
arr[i] = pair[i-1]-arr[0]
if __name__=='__main__':
pair = [15, 13, 11, 10, 12, 10, 9, 8, 7, 5]
n =5
arr = [0]*n
constructArr(arr,pair,n)
for i in range(n):
print(arr[i],end =" ")
|
C#
using System;
class PairSum
{
static 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];
}
public static void Main()
{
int []pair = {15, 13, 11, 10, 12,
10, 9, 8, 7, 5};
int n = 5;
int []arr = new int[n];
constructArr(arr, pair, n);
for (int i = 0; i < n; i++)
Console.Write(arr[i] + " ");
}
}
|
PHP
<?php
function constructArr($pair)
{
$arr = array();
$n = 5;
$arr[0] = intval(($pair[0] + $pair[1] -
$pair[$n - 1]) / 2);
for ($i = 1; $i < $n; $i++)
$arr[$i] = $pair[$i - 1] - $arr[0];
for ($i = 0; $i < $n; $i++)
echo $arr[$i] . " ";
}
$pair = array(15, 13, 11, 10,
12, 10, 9, 8, 7, 5);
constructArr($pair);
?>
|
Javascript
<script>
function constructArr(arr, pair, n)
{
arr[0] = Math.floor((pair[0]+pair[1]-pair[n-1]) / 2);
for (let i=1; i<n; i++)
arr[i] = pair[i-1]-arr[0];
}
let pair = [15, 13, 11, 10, 12, 10, 9, 8, 7, 5];
let n = 5;
let arr = new Array(n);
constructArr(arr, pair, n);
for (let i = 0; i < n; i++)
document.write(arr[i] + " ");
</script>
|
Output:
8 7 5 3 2
Time complexity of constructArr() is O(n) where n is number of elements in arr[].
Auxiliary Space: O(1)
Please write comments if you find anything incorrect, or you want to share more information about the topic discussed above.
Whether you're preparing for your first job interview or aiming to upskill in this ever-evolving tech landscape,
GeeksforGeeks Courses are your key to success. We provide top-quality content at affordable prices, all geared towards accelerating your growth in a time-bound manner. Join the millions we've already empowered, and we're here to do the same for you. Don't miss out -
check it out now!