Попарная сумма из n чисел в не возрастающем порядке

Question

Я видел этот вопрос в блоге по программированию .

Если попарные суммы чисел n даны в неубывающем порядке, укажите отдельные номера. Если сумма искажена, выведите -1.

Пример:

i/p: 4 5 7 10 12 13 

o/p: 1 3 4 9

Подсказки будет достаточно.

Answer 1

Позвольте B быть списком парных сумм, с B[0] <= B[1] <= ... <= B[m-1], и пусть A будет исходным списком чисел, которые мы пытаемся найти, с A[0] < A[1] < ... < A[n-1], где m = n(n-1)/2.

С учетом A[0], вычислить A за полиномиальное время

Построить A от наименьшего элемента к наибольшему.Предположим, что мы уже знаем A[0].Тогда, поскольку B[0] является наименьшим элементом в B, он может возникнуть только как A[0] + A[1].Точно так же B[1] должен равняться A[0] + A[2].Следовательно, если мы знаем A[0], мы можем вычислить A[1] и A[2].

После этого, однако, этот шаблон ломается.B[2] может быть A[0] + A[3] или A[1] + A[2], и без предварительного знания мы не можем знать, какой это.Однако, если мы знаем A[0], мы можем вычислить A[1] и A[2], как описано выше, а затем удалить A[1] + A[2] из B.Затем гарантируется, что следующим наименьшим элементом будет A[0] + A[3], что позволит нам найти A[3].Продолжая так, мы можем найти все A без возврата.Алгоритм выглядит примерно так:

for i from 1 to n-1 {
    // REMOVE SEEN SUMS FROM B
    for j from 0 to i-2 {
        remove A[j]+A[i-1] from B
    }
    // SOLVE FOR NEXT TERM
    A[i] = B[0] - A[0]
}
return A

Вот как это работает на вашем примере, где B = [4,5,7,10,12,13], если мы знаем A[0]=1:

start
    B = [4,5,7,10,12,13]
    A[0] = 1

i=1: 
    B = [4,5,7,10,12,13]
    A[1] = 4-1 = 3

i=2:
    Remove 1+3 from B
    B = [5,7,10,12,13]
    A[2] = 5-1 = 4

i=3:
    Remove 1+4 and 3+4 from B
    B = [10,12,13]
    A[3] = 10-1 = 9

end
    Remove 1+9 and 3+9 and 4+9 from B
    B = []
    A = [1,3,4,9]

Так что все сводится к знаниюA[0], из которого мы можем вычислить остаток A.

Вычислить A[0] за полиномиальное время

Теперь мы можем просто попробовать каждую возможность для A[0].Поскольку мы знаем B[0] = A[0] + A[1], мы знаем, что A[0] должно быть целым числом от 0 до B[0]/2 - 1.Мы также знаем, что

B[0] = A[0] + A[1]
B[1] = A[0] + A[2]

Более того, существует некоторый индекс i с 2 <= i <= n-1 такой, что

B[i] = A[1] + A[2]

Почему?Потому что единственные записи, потенциально меньшие A[1]+A[2], имеют форму A[0] + A[j], и таких выражений может быть не более n-1.Поэтому мы также знаем, что

A[0] = (B[0]+B[1] - B[i])/2

для некоторых 2 <= i <= n-1.Это, вместе с тем, что A[0] находится между 0 и B[0]/2-1, дает только несколько возможностей для A[0] для тестирования.

Например, есть две возможности для A[0]:0 или 1.Если мы попробуем алгоритм с A[0]=0, вот что произойдет:

start
    B = [4,5,7,10,12,13]
    A[0] = 0

i=1: 
    B = [4,5,7,10,12,13]
    A[1] = 4-0 = 4

i=2:
    Remove 0+4 from B
    B = [5,7,10,12,13]
    A[2] = 5-0 = 5

i=3:
    Remove 0+5 and 4+5 from B
    B = !!! PROBLEM, THERE IS NO 9 IN B!

end

Answer 2

Фердинанд Бейер был на верном пути, я думаю, прежде чем он удалил свой ответ.Чтобы повторить часть его подхода: у вас есть четыре неизвестных, a, b, c и d с a ≤ b ≤ c ≤ d.Исходя из этого, можно сформировать частичное упорядочение всех сумм:

a + b ≤ a + c
a + b ≤ a + d
a + c ≤ b + c
a + d ≤ b + d
a + d ≤ c + d
b + c ≤ b + d
b + d ≤ c + d

Если бы это был общий порядок, то было бы известно каждое из шести значений a + b, a + c, a + db + c, b + d и c + d.Тогда можно было бы следовать первоначальному плану Фердинанда и легко решать уравнения одновременности.

К сожалению, есть пара (a + d, b + c), которую можно упорядочить в любом случае.Но с этим достаточно легко справиться: предположим, что a + d < b + c (все входные значения различны, поэтому не нужно беспокоиться об использовании ≤) и попробуйте решить одновременные уравнения.Затем примите b + c < a + d и повторите.Если оба набора уравнений имеют решение, то у исходной задачи есть два ответа.Если ни один из наборов не имеет решения, тогда вывод должен быть -1.В противном случае у вас есть ваше (уникальное) решение.

Answer 3

Некоторые подсказки:

• Размер входа равен N * (N-1) / 2, поэтому вы можете определить размер вывода (т.е. 6 элементов на входесоответствует 4 элементам на выходе)

• Сумма входных данных представляет собой сумму выходных данных, деленную на N - 1 (то есть 1+3+4+9 = (4+5+7+10+12+13) / (4-1))

• Самый низкий и самый высокий входы являются суммой двух самых низких и двух самых высоких выходов соответственно (т.е. 4 = 1 + 3 и 13 = 4 + 9)

• Следующий самый низкий вход (5) отличается только на одно добавление от первого (1), поэтому вы можете вычислить одно из сложений, взяв разницу (5-1).

Answer 4

Недавно я проверял вопросы интервью и решил проблему с помощью подсказки @ PengOne для поиска первого значения,

Итак, если кому-то нужно законченное рабочее решение: Это в PHP:

сложность времени: O ((n * (n-2)) + 3 + n) с вспомогательными переменными. Пространственная сложность: почти такая же со временем сложность.

<?php
function getSublistSize($length)
{
    $i = 2;
    $n = 0;

    while ($i <= $length) {
        if (is_int($length / $i)) {
            if ($length == $i * ($i + 1) / 2) {
                return ($i + 1);
            }
        }

        ++$i;
    }

    return $n;
}

function findSubstractList(array $list)
{
    $length = count($list);

    $n = getSublistSize($length);
    $nth = $n - 1;

    $substractList = [];
    $substractTotal = array_sum($list) / ($length / 2); // A + B + C + D

    /**
     * formula : A = (list[0] + list[1] - list[nth -1]) / 2
     * list[0] = A + B,
     * list[1] = A + C,
     * list[nth - 1] = B + C
     *
     * =>  ((A + B) + (A + C) - (B + C)) / 2
     * => (A + A + (B + C - B - C)) / 2
     * => (2A + 0) / 2 => 2A / 2
     * => A
     */
    $substractList[] = (($list[0] + $list[1]) - $list[$nth]) / 2;

    for ($i = 0; $i < $nth; ++$i) {
        $substractList[] = ($list[$i] - $substractList[0]);
    }

//    $substractList[3] = $substractTotal - ($list[$nth - 1] + $substractList[0]);


    return $substractList;
}


$list = [5, 8, 14, 28, 40, 11, 17, 31, 43, 20, 34, 46, 40, 52, 66];

print_r(findSubstractList($list));

/**
 * P ) [6, 11, 101, 15, 105, 110];
 * S ) [1, 5, 10, 100]
 *
 * P ) [5, 8, 14, 28, 40, 11, 17, 31, 43, 20, 34, 46, 40, 52, 66];
 * S ) [1, 4, 7, 13, 27, 39]
 *
*/

Answer 5

Подход PengOne к восстановлению данных с заданными A [0] и B хорош, но есть лучший способ вычислить A [0].Обратите внимание, что два самых маленьких элемента B:

B[0] = A[0] + A[1]
B[1] = A[0] + A[2]

и

B[i] = A[1] + A[2]

для некоторого i.

Следовательно,

A[0] = (B[0] + B[1] - B[i]) / 2

для некоторых я, и нам просто нужно попробовать O (n ^ {1/2}) возможностей, так как я ограничен O (n ^ {1/2}), и посмотреть, приводит ли один к действительной установке оставшихсяэлементы A в соответствии с решением PengOne.Общее время работы O (n ^ {3/2}), где n - количество чисел на входе.

Answer 6

Я не уверен насчет самого быстрого алгоритма, но я могу объяснить, как это работает.

Первое число o / p - это разница между первым и вторым i / p

5-4=1

, так что теперь у вас есть первое число o / p.

Второе число o / p - это первое число i / p минус первое число o / p.

4-1=3

третья о / п - вторая о / п минус первая и / п

5-1=4