给定 n 个数字的成对和，求数字
原文:https://www . geesforgeks . org/given-pain-sum-n-numbers-find-numbers/
按指定顺序给出 n(其中 n >= 3)个数字的成对和，找出这些数字。该顺序具有第一和第二、第一和第三、第一和第四、…第二和第三、第二和第四，..等等。考虑一个例子:n = 4，让数字为{a，b，c，d}，它们的成对和以 arr[] = {a+b，a+c，a+d，b+c，b+d，c+d}的顺序给出。 示例:
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}
亚马逊提问
方法完全基于数学，如下所示:
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
以下是上述想法的实现。
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 program
int 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.
Python 3
# 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 Code
arr = [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...
服务器端编程语言（Professional Hypertext Preprocessor 的缩写）
<?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.
?>
java 描述语言
<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>
输出:
Numbers are: 3, 10, 7, 11, 6
时间复杂度:O(n) 参考文献: 【https://www.careercup.com/question?id=12005195】 本文由阿育什·乔哈里供稿。如果你喜欢 GeeksforGeeks 并想投稿，你也可以使用write.geeksforgeeks.org写一篇文章或者把你的文章邮寄到 contribute@geeksforgeeks.org。看到你的文章出现在极客博客主页上，帮助其他极客。 如果发现有不正确的地方，或者想分享更多关于上述话题的信息，请写评论。
版权属于：月萌API www.moonapi.com，转载请注明出处
