По заданной попарной сумме из n чисел найти числа

31.12.2019Массивы

Попарная сумма из 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 ++ программа для поиска n чисел из заданного упорядоченного
// попарная сумма из них.
#include <bits/stdc++.h>

using namespace std;

// Примечание: n - это не размер массива, а число
// элементы, чья попарная сумма хранится
// в обр []

void findNumbers(int arr[], int n)

{

int num[n];

// здесь вычисляется ба

int b_minus_a = arr[n-1] - arr[1];

// здесь вычисляется b

num[1] = (arr[0] + b_minus_a) / 2;

// здесь рассчитывается

num[0] = arr[0] - num[1];

// рассчитать все остальные числа

for (int i=1; i<=(n-2); i++)

num[i+1] = arr[i] - num[0];

// отображаем числа

cout << "Numbers are: ";

for (int i=0; i<n; i++)

cout << num[i] << " ";

}

// Драйвер программы

int main()

{

int arr[] = {13, 10, 14, 9, 17, 21, 16, 18, 13, 17};

int n = 5; // n это не размер массива, а число

// элементы, чья попарная сумма хранится

// в обр []

findNumbers(arr, n);

return 0;

}

Джава

// Java программа для поиска n чисел из заданного
// упорядоченная попарная сумма из них.

class GFG {

// Примечание: n это не размер массива, а число

// элементов, чья попарная сумма хранится

// в обр []

static void findNumbers(int arr[], int n)

{

int num[] = new int[n];

// здесь вычисляется ба

int b_minus_a = arr[n-1] - arr[1];

// здесь вычисляется b

num[1] = (arr[0] + b_minus_a) / 2;

// здесь рассчитывается

num[0] = arr[0] - num[1];

// рассчитать все остальные числа

for (int i = 1; i <= (n - 2); i++)

num[i+1] = arr[i] - num[0];

// отображаем числа

System.out.print("Numbers are: ");

for (int i = 0; i < n; i++)

System.out.print(num[i] + " ");

}

// Метод драйвера

public static void main(String[] args)

{

int arr[] = {13, 10, 14, 9, 17, 21,

16, 18, 13, 17};

// n это не размер массива, а число

// элементы, чья попарная сумма хранится

// в обр []

int n = 5;

findNumbers(arr, n);

}

// Этот код предоставлен Anant Agarwal.

python3

# Python3 программа для поиска n чисел
# из заданной упорядоченной попарной суммы из них.

# Примечание: n не является размером массива,
# но количество элементов, чьи
# попарная сумма хранится в arr []

def findNumbers(arr, n):

num = [0 for i in range(n)]

Здесь рассчитывается # ba

b_minus_a = arr[n-1] - arr[1]

# b рассчитывается здесь

num[1] = (arr[0] + b_minus_a) // 2

# а рассчитывается здесь

num[0] = arr[0] - num[1]

# рассчитать все остальные числа

for i in range(1, (n - 2) + 1):

num[i+1] = arr[i] - num[0]

# отобразить цифры

print("Numbers are: ", end = "")

for i in range(n):

print(num[i], end = ", ")

Код водителя

arr = [13, 10, 14, 9, 17, 21, 16, 18, 13, 17]

n = 5 # n не размер массива, а число

Количество элементов, чья попарная сумма равна

# хранится в arr []

findNumbers(arr, n)

# Этот код предоставлен Anant Agarwal.

C #

// C # программа для поиска n чисел из
// заданная упорядоченная попарная сумма из них.

using System;

class GFG {

// Примечание: n это не размер массива, а

// количество элементов, попарно

// сумма хранится в arr []

static void findNumbers(int []arr, int n)

{

int []num = new int[n];

// здесь вычисляется ба

int b_minus_a = arr[n - 1] - arr[1];

// здесь вычисляется b

num[1] = (arr[0] + b_minus_a) / 2;

// здесь рассчитывается

num[0] = arr[0] - num[1];

// рассчитать все остальные числа

for (int i = 1; i <= (n - 2); i++)

num[i + 1] = arr[i] - num[0];

// отображаем числа

Console.Write("Numbers are: ");

for (int i = 0; i < n; i++)

Console.Write(num[i] + " ");

}

// Код драйвера

public static void Main(String[] args)

{

int []arr = {13, 10, 14, 9, 17,

21, 16, 18, 13, 17};

// n это не размер массива, а число

// элементы, чья попарная сумма хранится

// в обр []

int n = 5;

findNumbers(arr, n);

}

// Этот код предоставлен parashar ...

PHP

<?php
// PHP программа для поиска n чисел
// из заданного упорядоченного попарно
// сумма из них.

// Примечание: n не размер
// массива, но номер
// элементы, чьи попарно
// сумма хранится в arr []

function findNumbers($arr, $n)

{

$num[$n]=0;

// здесь вычисляется ба

$b_minus_a = $arr[$n - 1] - $arr[1];

// здесь вычисляется b

$num[1] = ($arr[0] + $b_minus_a) / 2;

// здесь рассчитывается

$num[0] = $arr[0] - $num[1];

// рассчитать все остальные числа

for($i = 1; $i <= ($n - 2); $i++)

$num[$i + 1] = $arr[$i] - $num[0];

// отображаем числа

echo "Numbers are: ";

for($i = 0; $i < $n; $i++)

echo $num[$i]. ", ";

}

// Код драйвера
{

$arr = array(13, 10, 14, 9, 17,

21, 16, 18, 13, 17);

// n это не размер массива, а число

// элементы, чья попарная сумма хранится

// в обр []

$n = 5;

findNumbers($arr, $n);

return 0;

}

// Этот код предоставлен нитин митталь.
?>

Выход:

Numbers are: 3, 10, 7, 11, 6

Сложность времени: O (n)

Ссылки:
https://www.careercup.com/question?id=12005195

Эта статья предоставлена Аюшем Джаухари . Если вы как GeeksforGeeks и хотели бы внести свой вклад, вы также можете написать статью с помощью contribute.geeksforgeeks.org или по почте статьи contribute@geeksforgeeks.org. Смотрите свою статью, появляющуюся на главной странице GeeksforGeeks, и помогите другим вундеркиндам.

Пожалуйста, пишите комментарии, если вы обнаружите что-то неправильное или вы хотите поделиться дополнительной информацией по обсуждаемой выше теме.

Рекомендуемые посты:

По заданной попарной сумме из n чисел найти числа

0.00 (0%) 0 votes