JavaScript Program to Construct an Array from its pair-sum Array
Last Updated :
18 Sep, 2023
The pair-sum array is a unique construction that holds the sum of all potential pairs of elements from the original array. At first glance, it might appear to be challenging, but in this article, we'll Construct an array from its pair-sum array and discover some of its most intriguing uses.
What is Pair - Sum Array?
A pair-sum array in JavaScript is an array that holds the total number of potential pairs of elements from the original array. The pair-sum array, designated as pairSumArr, will have a length of n*(n-1)/2 when an array arr of length n is given. This is because it contains the sum of all conceivable combinations of two entries from the original array.
Example 1:
Suppose we have the original array arr = [2, 5, 7]. The pair-sum array will be:
pairSumArr = [2+5, 2+7, 5+7] = [7, 9, 12]
Here, pairSumArr[0] contains the sum of the first two elements of arr, i.e., 2 + 5 = 7.
Similarly, pairSumArr[1] contains the sum of the first and last elements of arr, i.e., 2 + 7 = 9,
and pairSumArr[2] contains the sum of the last two elements of arr, i.e., 5 + 7 = 12
Example 2:
2. If we take another example Suppose we have the original array arr = [3, 6, 8, 2].
We will construct the pair-sum array for this array.
pairSumArr = [3+6, 3+8, 3+2, 6+8, 6+2, 8+2]
pairSumArr = [9, 11, 5, 14, 8, 10]
Use of Pair - Sum Array
- Array Reconstruction: If the pair-sum array is known, it can be used to rebuild the original array. In this procedure, the sum array is reverse-engineered to get the elements of the original array.
- Combinatorics: Applications of the pair-sum array include combinatorial issues, particularly when array combinations are involved.
- Optimization Problems: The pair-sum array can assist in identifying patterns and connections between items in some optimization problems, resulting in optimum solutions.
- Finding Missing Elements: When some items of an array are lost but their pairwise sums are still available, the pair-sum array can be useful. We may determine the elements that are missing by using the pair-sum array.
Constructing the Original Array from Pair-Sum Array
In JavaScript, we may apply a straightforward approach to create an array from its pair-sum array. The approach includes reconstructing the original array by going backward through the pair-sum array generation process given the pair-sum array pairSumArr. The fundamental concept is to use the provided pair-sum array to identify the original array's missing items. We must reverse engineer the pair-sum array's generation in order to create the original array from its pair-sum array. We may effectively rebuild the original array by recognizing the pattern and using the right algorithm.
Approach
The basic algorithm to construct an original array from a pair-sum array includes the following steps as follow.
- Create an array of size n to store the original array elements.
- Iterate n times and find the missing elements of the original array by performing reverse operations on the pair-sum array.
- Calculate the length of the pair-sum array.
- Calculate the length of the Original Array from the given Pair Sum Array.
- Return the reconstructed
Example:
JavaScript
// Function to construct original array
// from pair sum array
function constructArr(pair, n) {
let arr = new Array(n);
// Calculate the first element of
// the original array
// first element = (pair[0] + pair[1]
// - pair[n-1]) / 2
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];
return arr;
}
// Function to calculate the length of the
// original array from the given pair sum array
function calculateOriginalArrayLength(pairSumArrayLength) {
return Math.ceil(
(Math.sqrt(8 * pairSumArrayLength + 1) + 1) / 2
);
}
// Given pair sum array
let pair = [13, 11, 10, 13, 10, 9, 12, 7, 10, 9];
// Calculate the length of the pair sum array
const arrayLength = pair.length;
// Calculate the length of the original array
const originalArrayLength =
calculateOriginalArrayLength(arrayLength);
// Number of elements in the original array
let n = originalArrayLength;
// Create an array which can store original array
let originalArr = constructArr(pair, n);
// Required Original array from the Pair sum Array
console.log("Original Array:", originalArr);
OutputOriginal Array: [ 7, 6, 4, 3, 6 ]
Similar Reads
Javascript Program to Count pairs with given sum Given an array of integers, and a number 'sum', find the number of pairs of integers in the array whose sum is equal to 'sum'.Note: Duplicate pairs are also allowed. Examples: Input : arr[] = {1, 5, 7, -1}, sum = 6 Output : 2 Pairs with sum 6 are (1, 5) and (7, -1) Input : arr[] = {1, 5, 7, -1, 5},
2 min read
Javascript Program for Find k pairs with smallest sums in two arrays Given two integer arrays arr1[] and arr2[] sorted in ascending order and an integer k. Find k pairs with smallest sums such that one element of a pair belongs to arr1[] and other element belongs to arr2[]Examples: Input : arr1[] = {1, 7, 11} arr2[] = {2, 4, 6} k = 3Output : [1, 2], [1, 4], [1, 6]Exp
3 min read
Javascript Program for Largest Sum Contiguous Subarray Write an efficient program to find the sum of contiguous subarray within a one-dimensional array of numbers that has the largest sum. Kadane's Algorithm:Initialize: max_so_far = INT_MIN max_ending_here = 0Loop for each element of the array (a) max_ending_here = max_ending_here + a[i] (b) if(max_so_f
5 min read
How to Find Matching Pair from an Array in PHP ? Given an Array, the task is to find the matching pair from a given array in PHP. Matching a pair from an array involves searching for two elements that satisfy a certain condition, such as having the same value, summing up to a specific target, or meeting some other criteria. Here, we will cover thr
5 min read
Javascript Program for Number of pairs with maximum sum Write a javascript program for a given array arr[], count the number of pairs arr[i], arr[j] such that arr[i] + arr[j] is maximum and i < j. Example: Input : arr[] = {1, 1, 1, 2, 2, 2}Output: 3Explanation: The maximum possible pair sum where i<j is 4, which is given by 3 pairs, so the answer i
3 min read
Java Program to Merge Two Arrays In Java, merging two arrays is a good programming question. We have given two arrays, and our task is to merge them, and after merging, we need to put the result back into another array. In this article, we are going to discuss different ways we can use to merge two arrays in Java.Let's now see the
5 min read
Calculate the Sum and Average of Elements in an ArrayList in Java A Dynamic and Adaptable method for storing and managing collections of elements is to use ArrayList. Finding the total and average of an ArrayList's items is frequently required when working with numerical data that is stored in the list. In this article, we will see how we can sum and find the aver
3 min read
PHP Program for Number of pairs with maximum sum Write a PHP program for a given array arr[], count the number of pairs arr[i], arr[j] such that arr[i] + arr[j] is maximum and i < j.Example:Input : arr[] = {1, 1, 1, 2, 2, 2} Output: 3 Explanation: The maximum possible pair sum where i<j is 4, which is given by 3 pairs, so the answer is 3 the
3 min read
Java Program to Compute the Sum of Numbers in a List Using Recursion ArrayList is a part of the Collection framework and is present in java.util package. It provides us with dynamic arrays in Java. Though, it may be slower than standard arrays but can be helpful in programs where lots of manipulation in the array is needed. This class is found in java.util package. I
5 min read
Print all pairs in an unsorted array with equal sum Given an unsorted array A[]. The task is to print all unique pairs in the unsorted array with equal sum. Note: Print the result in the format as shown in the below examples. Examples: Input: A[] = { 6, 4, 12, 10, 22, 54, 32, 42, 21, 11} Output: Pairs : ( 4, 12) ( 6, 10) have sum : 16 Pairs : ( 10, 2
13 min read