Pairwise sum of n (where n >= 3) numbers are given in a specified order, find the numbers. The order has pair sum of first and second, then first and third, first and fourth, … second and third, second and fourth, .. and so on. Consider an example: n = 4, let the numbers be {a, b, c, d}, their pairwise sum is given in the order arr[] = {a+b, a+c, a+d, b+c, b+d, c+d}.
Examples:
Input : arr[] = {11, 18, 13, 13, 8, 5}
Output : {8, 3, 10, 5}
8+3 = 11, 8+10 = 18, 8+5 = 13, 3+10 = 13,
3+5 = 8, ...
Input : arr[] = {13, 10, 14, 9, 17, 21,
16, 18, 13, 17}
Output : {3, 10, 7, 11, 6}
Asked in Amazon
Approach is purely based on mathematics which is illustrated below:
n = 3, {a+b, a+c, b+c}
We can find b-a = arr[2] - arr[1]
= (b+c) - (a+c)
We can find b = (arr[0] + (b-a))/2
= (a + b + (b - a))/2
= b
We can find a = arr[0] - b
= a
n = 4, {a+b, a+c, a+d, b+c, b+d, c+d}
We can find b-a = arr[3] - arr[1]
= (b+c) - (a+c)
We can find b = (arr[0] + (b-a)) / 2
= ((a+b) + (b-a)) / 2
a = arr[0] - b
= (a+b) - b
c = arr[1] - a
= (a+c) - a
d = arr[2] - a
= (a+d) - a
Observation :
b_minus_a = b - a = arr[n-1] - arr[1]
b = (arr[0] + b_minus_a)/2
a = (arr[0] - b)
c = arr[1] - a
d = arr[2] - a
..........
n = 5, {a+b, a+c, a+d, a+e, b+c,
b+d, b+e, c+d, c+e, d+e}
Then calculate b-a = arr[n-1] - arr[1]
= (b+c) - (a+c)
Then b = (arr[0] + (b-a)) / 2
= ((a+b) + (b-a)) / 2
a = arr[0] - b
= (a+b) - b
Then for i=1 to n-2,
remaining numbers are calculated as
arr[i] - a, like
c = arr[1] - a
= (a+c) - a
d = arr[2] - a
= (a+c) - a and so on,
.
.
.
.
last number = arr[n-2] - a
Below is the implementation of above idea.
C++
// C++ program to find n numbers from given ordered// pairwise sum of them.#include <bits/stdc++.h>using namespace std;// Note : n is not size of array, but number of// elements whose pairwise sum is stored// in arr[]void findNumbers(int arr[], int n){ int num[n]; // b-a is calculated here int b_minus_a = arr[n-1] - arr[1]; // b is calculated here num[1] = (arr[0] + b_minus_a) / 2; // a is calculated here num[0] = arr[0] - num[1]; // to calculate all the other numbers for (int i=1; i<=(n-2); i++) num[i+1] = arr[i] - num[0]; // display the numbers cout << "Numbers are: "; for (int i=0; i<n; i++) cout << num[i] << " ";}//Driver programint main(){ int arr[] = {13, 10, 14, 9, 17, 21, 16, 18, 13, 17}; int n = 5; // n is not size of array, but number of // elements whose pairwise sum is stored // in arr[] findNumbers(arr, n); return 0;} |
Java
// Java program to find n numbers from given // ordered pairwise sum of them.class GFG { // Note : n is not size of array, but number // of elements whose pairwise sum is stored // in arr[] static void findNumbers(int arr[], int n) { int num[] = new int[n]; // b-a is calculated here int b_minus_a = arr[n-1] - arr[1]; // b is calculated here num[1] = (arr[0] + b_minus_a) / 2; // a is calculated here num[0] = arr[0] - num[1]; // to calculate all the other numbers for (int i = 1; i <= (n - 2); i++) num[i+1] = arr[i] - num[0]; // display the numbers System.out.print("Numbers are: "); for (int i = 0; i < n; i++) System.out.print(num[i] + " "); } // Driver method public static void main(String[] args) { int arr[] = {13, 10, 14, 9, 17, 21, 16, 18, 13, 17}; // n is not size of array, but number of // elements whose pairwise sum is stored // in arr[] int n = 5; findNumbers(arr, n); }}// This code is contributed by Anant Agarwal. |
Python3
# Python3 program to find n numbers # from given ordered pairwise sum of them.# Note : n is not size of array,# but number of elements whose# pairwise sum is stored in arr[]def findNumbers(arr, n): num = [0 for i in range(n)] # b-a is calculated here b_minus_a = arr[n-1] - arr[1] # b is calculated here num[1] = (arr[0] + b_minus_a) // 2 # a is calculated here num[0] = arr[0] - num[1] # to calculate all the other numbers for i in range(1, (n - 2) + 1): num[i+1] = arr[i] - num[0] # display the numbers print("Numbers are: ", end = "") for i in range(n): print(num[i], end = ", ")# Driver Codearr = [13, 10, 14, 9, 17, 21, 16, 18, 13, 17]n = 5 # n is not size of array, but number # of elements whose pairwise sum is # stored in arr[] findNumbers(arr, n)# This code is contributed by Anant Agarwal. |
C#
// C# program to find n numbers from // given ordered pairwise sum of them. using System;class GFG { // Note : n is not size of array, but // number of elements whose pairwise // sum is stored in arr[] static void findNumbers(int []arr, int n) { int []num = new int[n]; // b-a is calculated here int b_minus_a = arr[n - 1] - arr[1]; // b is calculated here num[1] = (arr[0] + b_minus_a) / 2; // a is calculated here num[0] = arr[0] - num[1]; // to calculate all the other numbers for (int i = 1; i <= (n - 2); i++) num[i + 1] = arr[i] - num[0]; // display the numbers Console.Write("Numbers are: "); for (int i = 0; i < n; i++) Console.Write(num[i] + " "); } // Driver code public static void Main(String[] args) { int []arr = {13, 10, 14, 9, 17, 21, 16, 18, 13, 17}; // n is not size of array, but number of // elements whose pairwise sum is stored // in arr[] int n = 5; findNumbers(arr, n); }}// This code is contributed by parashar... |
PHP
<?php// PHP program to find n numbers // from given ordered pairwise // sum of them.// Note : n is not size// of array, but number of// elements whose pairwise// sum is stored in arr[]function findNumbers($arr, $n){ $num[$n]=0; // b-a is calculated here $b_minus_a = $arr[$n - 1] - $arr[1]; // b is calculated here $num[1] = ($arr[0] + $b_minus_a) / 2; // a is calculated here $num[0] = $arr[0] - $num[1]; // to calculate all the other numbers for($i = 1; $i <= ($n - 2); $i++) $num[$i + 1] = $arr[$i] - $num[0]; // display the numbers echo "Numbers are: "; for($i = 0; $i < $n; $i++) echo $num[$i]. ", ";}// Driver Code{ $arr = array(13, 10, 14, 9, 17, 21, 16, 18, 13, 17); // n is not size of array, but number of // elements whose pairwise sum is stored // in arr[] $n = 5; findNumbers($arr, $n); return 0;}// This code is contributed by nitin mittal.?> |
Javascript
<script>// javascript program to find n numbers from given // ordered pairwise sum of them. // Note : n is not size of array, but number // of elements whose pairwise sum is stored // in arr function findNumbers(arr , n) { var num = Array(n).fill(0); // b-a is calculated here var b_minus_a = arr[n - 1] - arr[1]; // b is calculated here num[1] = parseInt((arr[0] + b_minus_a) / 2); // a is calculated here num[0] = arr[0] - num[1]; // to calculate all the other numbers for (i = 1; i <= (n - 2); i++) num[i + 1] = arr[i] - num[0]; // display the numbers document.write("Numbers are: "); for (i = 0; i < n; i++) document.write(num[i] + " "); } // Driver method var arr = [ 13, 10, 14, 9, 17, 21, 16, 18, 13, 17 ]; // n is not size of array, but number of // elements whose pairwise sum is stored // in arr var n = 5; findNumbers(arr, n);// This code contributed by umadevi9616 </script> |
Output
Numbers are: 3 10 7 11 6
Time Complexity: O(n)
This article is contributed by Ayush Jauhari. If you like neveropen and would like to contribute, you can also write an article using write.geeksforgeeks.org or mail your article to review-team@geeksforgeeks.org. See your article appearing on the neveropen main page and help other Geeks.
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
