Рубрики

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

Попарная сумма из 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