Construya una array a partir de su array de suma de pares

Dado un arreglo de suma de pares y el tamaño del arreglo original (n), construya el arreglo original.
Una array de suma de pares para una array es la array que contiene la suma de todos los pares en forma ordenada. Por ejemplo, la array de suma de pares para arr[] = {6, 8, 3, 4} es {14, 9, 10, 11, 12, 7}.
En general, la array de suma de pares para arr[0..n-1] es {arr[0]+arr[1], arr[0]+arr[2], ……., arr[1]+arr[ 2], array[1]+array[3], ……., array[2]+array[3], array[2]+array[4], …., array[n-2]+array[n -1}.
«Dada una array de suma de pares, construya la array original».
Le recomendamos encarecidamente que minimice su navegador e intente hacerlo usted mismo.
Deje que la array dada sea «par []» y que haya n elementos en la array original. Si echamos un vistazo a algunos ejemplos, podemos observar que arr[0] es la mitad de par[0] + par[1] – par[n-1]. Tenga en cuenta que el valor de par[0] + par[1] – par[n-1] es (arr[0] + arr[1]) + (arr[0] + arr[2]) – (arr[1 ] + arr[2]). 
Una vez que hemos evaluado arr[0], podemos evaluar otros elementos restando arr[0]. Por ejemplo, arr[1] se puede evaluar restando arr[0] del par[0], arr[2] se puede evaluar restando arr[0] del par[1].
A continuación se muestra la implementación de la idea anterior.
 

#include <bits/stdc++.h>
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;
}

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 */

# 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# 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
// 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
?>

<script>
 
// Fills element in arr[] from
// its pair sum array pair[].
// n is size of arr[]
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];
}
 
// Driver program to test above function
 
    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] + " ");
 
 
// This code is contributed by Surbhi Tyagi.
 
</script>

Producción:  

 8 7 5 3 2 

La complejidad temporal de constructArr() es O(n) donde n es el número de elementos en arr[].

Espacio auxiliar: O(1)
Este artículo es una contribución de Abhishek. Escriba comentarios si encuentra algo incorrecto o si desea compartir más información sobre el tema tratado anteriormente.