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 <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[0] = (pair[0]+pair[1]-pair[n-1]) / 2; for ( int i=1; i<n; i++) arr[i] = pair[i-1]-arr[0]; } // 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; } |
Java
import java.io.*; class PairSum { // Fills element in arr[] from its pair sum array pair[]. // n is size of arr[] 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 ]; } // Driver program to test above function 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]+ " " ); } } /* This code is contributed by Devesh Agrawal */ |
Python3
# Fills element in arr[] from its # pair sum array pair[]. # n is size of arr[] 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 ] # Driver code 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 = " " ) # This code is contributed by # Shrikant13 |
C#
// C# program to construct an // array from its pair-sum array using System; class PairSum { // Fills element in arr[] from its // pair sum array pair[]. // n is size of arr[] 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]; } // Driver program to test above function 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] + " " ); } } // This code is contributed by nitin mittal |
PHP
<?php // Fills element in arr[] from // its pair sum array pair[]. // n is size of arr[] 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 ] . " " ; } // Driver Code $pair = array (15, 13, 11, 10, 12, 10, 9, 8, 7, 5); constructArr( $pair ); // This code is contributed by Sam007 ?> |
Output :
8 7 5 3 2
Time complexity of constructArr() is O(n) where n is number of elements in arr[].
leave a comment
0 Comments