Пареальная сумма n чисел в неупорядоченном порядке
Я видел этот вопрос в блоге интервью .
Если попарные суммы чисел n
приведены в неубывающем порядке, определите отдельные числа. Если сумма повреждена, напечатайте -1
.
Пример:
i/p: 4 5 7 10 12 13
o/p: 1 3 4 9
Достаточно намека.
Ответы
Ответ 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
Ответ 2
Некоторые подсказки:
-
Размер ввода - 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).
Ответ 3
Фердинанд Бейер, кажется, был на правильном пути, прежде чем удалил свой ответ. Повторить часть его подхода: у вас есть четыре неизвестных, 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 + d
, b + c
, b + d
и c + d
. Затем можно было бы следовать первоначальному плану Фердинанда и легко решить одновременные уравнения.
К сожалению, существует пара (a + d
, b + c
), которую можно упорядочить в любом случае. Но это достаточно легко справиться: предположим, что a + d < b + c
(входные значения различны, поэтому вам не нужно беспокоиться об использовании ≤) и попытайтесь решить одновременные уравнения. Тогда предположим b + c < a + d
и повторите. Если обе системы уравнений имеют решение, то исходная задача имеет два ответа. Если ни один из них не имеет решения, выход должен быть -1
. В противном случае у вас есть свое (уникальное) решение.
Ответ 4
Подход 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
для некоторого i, и нам просто нужно попробовать возможности O (n ^ {1/2}), так как я ограничено O (n ^ {1/2}) и посмотрим, приводит ли оно к допустимой настройке из оставшихся элементов решения A на PengOne. Общее время работы - O (n ^ {3/2}), где n - количество чисел на входе.
Ответ 5
Недавно я проверял вопросы интервью, и я решил проблему с помощью подсказки @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]
*
*/
Ответ 6
Я не уверен в самом быстром алгоритме, но я могу объяснить, как это работает.
Первое число o/p, является разницей между первым и вторым i/p
5-4=1
так что теперь у вас есть первый номер o/p.
Второе число o/p - первое i/p минус первое o/p.
4-1=3
третья часть o/p - вторая o/p минус первая i/p
5-1=4