Construct an array from its pair-sum array

Given a pair-sum array arr[], construct the original array res[] where each element in arr represents the sum of a unique pair from res in a specific order, starting with res[0] + res[1], then res[0] + res[2], and so on through all combinations where the first index is less than the second.

Note: The size of the input array will always be n * (n - 1) / 2, which corresponds to the number of such unique pairs for an original array of size n. It's important to note that not every array arr[] corresponds to a valid original array res[]. It's also possible for multiple valid original arrays to exist that produce the same pair-sum array.

Examples

Input: arr[] = [4, 5, 3]
Output: [3, 1, 2]
Explanation: For [3, 1, 2], pairwise sums are (3 + 1), (3 + 2) and (1 + 2)

Input: arr[] = [3]
Output: [1, 2]
Explanation: There may be multiple valid original arrays that produce the same pair-sum array, such as [1, 2] and [2, 1]. Both are considered correct since they yield the same set of pairwise sums.

Approach:

The approach begins by calculating the size n of the original array using the length of the pair-sum array. It then uses the first few sums in arr to compute the first element of the original array by subtracting one sum from the others in a way that isolates it. Once the first element is known, the rest of the elements can be found by subtracting it from the corresponding pair sums.

Illustration:

Once the value of n (the size of the original array) and res[0] (the first element of the original array) is determined, the rest of the array can be reconstructed by using the structure of the pair-sum array. Since the initial elements of arr represent sums of res[0] with each of the remaining elements, we can simply subtract res[0] from each of these to get the other values. Specifically, for each i from 1 to n-1, res[i] can be found as arr[i-1] - res[0].

#include <iostream> #include <vector> #include <cmath> using namespace std; vector<int> constructArr(vector<int>& arr) {    if(arr.size() == 1)   return {1, arr[0]-1} ;    // Size of the result array  int n = (1 + sqrt(1 + 8 * arr.size())) / 2;    // Find the result array  vector<int> res(n);  res[0] = (arr[0] + arr[1] - arr[n - 1]) / 2;  for (int i = 1; i < n; i++)  res[i] = arr[i - 1] - res[0];    return res; } // Driver program to test the function int main() {  vector<int> arr = {4, 5, 3};  vector<int> res = constructArr(arr);  for (int x : res)  cout << x << " ";  return 0; } 

import java.util.ArrayList; import java.util.List; class GfG {  public static ArrayList<Integer> constructArr(int[] arr) {    // only one pair-sum ⇒ original array has two numbers  if (arr.length == 1) {  return new ArrayList<>(List.of(1, arr[0] - 1));  }  // Compute n from m = n·(n−1)/2 ⇒ n = (1 + √(1 + 8m)) / 2  int n = (int) ((1 + Math.sqrt(1 + 8 * arr.length)) / 2);  int[] res = new int[n];    // res[0] is obtained from the first three relevant sums  res[0] = (arr[0] + arr[1] - arr[n - 1]) / 2;  // Remaining elements: subtract res[0] from successive pair sums  for (int i = 1; i < n; i++) {  res[i] = arr[i - 1] - res[0];  }  ArrayList<Integer> ans = new ArrayList<>(n);  for (int x : res) ans.add(x);  return ans;  }  public static void main(String[] args) {    int[] arr = {4, 5, 3};  ArrayList<Integer> res = constructArr(arr);    for (int x : res) System.out.print(x + " ");  } } 

import math def constructArr(arr): # When the pair-sum array has only one element, # the original array must have exactly two numbers. if len(arr) == 1: return [1, arr[0] - 1] # Size of the original array  n = int((1 + math.isqrt(1 + 8 * len(arr))) / 2) # Reconstruct the original array res = [0] * n res[0] = (arr[0] + arr[1] - arr[n - 1]) // 2 for i in range(1, n): res[i] = arr[i - 1] - res[0] return res # Driver code if __name__ == "__main__": arr = [4, 5, 3] res = constructArr(arr) print(' '.join(map(str, res))) 

using System; using System.Collections.Generic; class GfG{    static List<int> constructArr(int[] arr){    // only one pair-sum ⇒ original array has two numbers  if (arr.Length == 1)  return new List<int> { 1, arr[0] - 1 };  // Compute n from m = n·(n−1)/2 ⇒ n = (1 + √(1 + 8m)) / 2  int n = (int)((1 + Math.Sqrt(1 + 8 * arr.Length)) / 2);  int[] res = new int[n];    // res[0] is obtained from the first three relevant sums  res[0] = (arr[0] + arr[1] - arr[n - 1]) / 2;  // Remaining elements: subtract res[0] from successive pair sums  for (int i = 1; i < n; i++)  res[i] = arr[i - 1] - res[0];  return new List<int>(res);  }  static void Main(){    int[] arr = { 4, 5, 3 };  List<int> res = constructArr(arr);  foreach (int x in res) Console.Write(x + " ");  } } 

function constructArr(arr) {    // only one pair-sum   // the original array has exactly two numbers  if (arr.length === 1) {  return [1, arr[0] - 1];  }  // Size of the original array  const n = Math.floor((1 + Math.sqrt(1 + 8 * arr.length)) / 2);  // Reconstruct the original array  const res = new Array(n);  res[0] = (arr[0] + arr[1] - arr[n - 1]) / 2;  for (let i = 1; i < n; i++) {  res[i] = arr[i - 1] - res[0];  }  return res; } // Driver code const arr = [4, 5, 3]; const res = constructArr(arr); console.log(res.join(' '));  

3 1 2 

Time Complexity: O(n), where n is the size of the original array, since we compute each element of res[] in a single pass.
Auxiliary Space: O(n), for storing the output array res[], no extra space is used beyond that.