Найти удаленное число

wanderer · Post by **wanderer** » 27 Dec 2001 22:28

Дан массив X[N] несортированных целых чисел. Второй массив Y[N-1] получен удалением из X одного числа. Определить удаленное число (но не обязательно его положение в массиве X) наибыстрым образом.

Подсказка - как это можно было бы ЗАПРОГРАММИРОВАТЬ?

[ 27-12-2001: Message edited by: wanderer ]

Andy77 · Post by **Andy77** » 27 Dec 2001 23:05

<blockquote>:<hr>Originally posted by wanderer:
Дан массив X[N] несортированных целых чисел. Второй массив Y[N-1] получен удалением из X одного числа. Определить удаленное число (но не обязательно его положение в массиве X) наибыстрым образом.

[ 27-12-2001: Message edited by: wanderer ]<hr></blockquote>
методом деления пополам? [img:bd4ba1b278]images/smiles/icon_confused.gif[/img:bd4ba1b278]

Andy77 · Post by **Andy77** » 27 Dec 2001 23:10

а если массив Y после удаления элемента еще и перемешали, то получается линейная сложность, если допустить, что мы можем использовать кусок памяти размером MAX(X) [img:3d70f54aed]images/smiles/icon_wink.gif[/img:3d70f54aed]

Kisena · Post by **Kisena** » 27 Dec 2001 23:10

<blockquote>quote:<hr>Originally posted by Andy77:
<blockquote>:<hr>Originally posted by wanderer:
[qb]Дан массив X[N] несортированных целых чисел. Второй массив Y[N-1] получен удалением из X одного числа. Определить удаленное число (но не обязательно его положение в массиве X) наибыстрым образом.

[ 27-12-2001: Message edited by: wanderer ]<hr></blockquote>
методом деления пополам? [img:fbe19d8891]images/smiles/icon_confused.gif[/img:fbe19d8891] [/QB]<hr></blockquote>

Если в массиве одно и то же число может появляться несколько раз, то не очень понятно, как реализовывать метод деления пополам.

Andy77 · Post by **Andy77** » 27 Dec 2001 23:20

<blockquote>quote:<hr>Originally posted by Kisena:


Если в массиве одно и то же число может появляться несколько раз, то не очень понятно, как реализовывать метод деления пополам.<hr></blockquote>

точно так же как и в случае с уникальными числами... делим отрезок пополам, пока не наткнемся на
[b:8930d7f0db]n : X[n]!=Y[n]&& X[n-1]==Y[n-1][/b:8930d7f0db]

[ 27-12-2001: Message edited by: Andy77 ]

Drom · Post by **Drom** » 27 Dec 2001 23:42

<blockquote>quote:<hr>Originally posted by Andy77:
а если массив Y после удаления элемента еще и перемешали, то получается линейная сложность, если допустить, что мы можем использовать кусок памяти размером MAX(X) [img:2f0bbdded9]images/smiles/icon_wink.gif[/img:2f0bbdded9] <hr></blockquote>

наверное, это и имелось в виду. в остальных случаях проще найти число _вместе_ с его индексом.

wanderer?

wanderer · Post by **wanderer** » 28 Dec 2001 00:42

Поскольку не сказано что числа все разные, то ... хмм ... они могут быть одинаковы. Поэтому, вопрос о положении удаленного элемента в общем случае неразрешим. Ну разве что попросить положение КАКОГО НИБУДЬ элемента с тем же значением. Но и этого не спрашивается. Все что спрашивается, это какое ЧИСЛО было удалено, где бы оно не находилось.

Также, элементы второго массива не обязанны быть расположенными в том же порядке. Извиняюсь если из условия это было не очень ясно.

[ 27-12-2001: Message edited by: wanderer ]

Andy77 · Post by **Andy77** » 28 Dec 2001 02:46

<blockquote>quote:<hr>Originally posted by wanderer:
Поскольку не сказано что числа все разные, то ... хмм ... они могут быть одинаковы. Поэтому, вопрос о положении удаленного элемента в общем случае неразрешим. Ну разве что попросить положение КАКОГО НИБУДЬ элемента с тем же значением. Но и этого не спрашивается. Все что спрашивается, это какое ЧИСЛО было удалено, где бы оно не находилось.

Также, элементы второго массива не обязанны быть расположенными в том же порядке. Извиняюсь если из условия это было не очень ясно.

[ 27-12-2001: Message edited by: wanderer ]<hr></blockquote>

Тогда считаем суммы первого и второго массива - сойдёт?

Chapaev · Post by **Chapaev** » 28 Dec 2001 02:51

<blockquote>quote:<hr>Originally posted by wanderer:
Дан массив X[N] несортированных целых чисел. Второй массив Y[N-1] получен удалением из X одного числа. Определить удаленное число (но не обязательно его положение в массиве X) наибыстрым образом.

Подсказка - как это можно было бы ЗАПРОГРАММИРОВАТЬ?<hr></blockquote>

Я бы отсортировал оба массива X и Y функцией qsort. А затем
for(int i=0; i<N-1; i++)
if(X[i] != Y[i])
return X[i];
return X[N-1];

Chapaev · Post by **Chapaev** » 28 Dec 2001 02:55

<blockquote>quote:<hr>Originally posted by Andy77:


Тогда считаем суммы первого и второго массива - сойдёт?<hr></blockquote>

Просто и красиво!

Drom · Post by **Drom** » 28 Dec 2001 03:00

<blockquote>quote:<hr>Originally posted by Chapaev:

Я бы отсортировал оба массива X и Y функцией qsort. А затем...<hr></blockquote>

сложность у quicksort'а (что нас в этой задаче и заботит) N * log(N) - больше чем линейная.

wanderer · Post by **wanderer** » 28 Dec 2001 03:34

<blockquote>quote:<hr>Originally posted by Andy77:


Тогда считаем суммы первого и второго массива - сойдёт?<hr></blockquote>

Для математика сойдет вполне [img:430f246ab8]images/smiles/icon_smile.gif[/img:430f246ab8] И действительно, просто и красиво.

Теперь для программистов: предположим, что мы используем такой тип целых чисел, что любая операция сложения или вычитания может вызвать переполнение [img:430f246ab8]images/smiles/icon_sad.gif[/img:430f246ab8]

Тогда как ?

Kisena · Post by **Kisena** » 28 Dec 2001 03:42

А сравнивать можно? Насколько мы помним, сравнение двух чисел производится путем сравнения их разницы с нулем. Или теперь так не делают? Или никогда так не делали?

Drom · Post by **Drom** » 28 Dec 2001 03:44

<blockquote>quote:<hr>Originally posted by wanderer:
Теперь для программистов: предположим, что мы используем такой тип целых чисел, что любая операция сложения или вычитания может вызвать переполнение [img:45b8d2a598]images/smiles/icon_sad.gif[/img:45b8d2a598]

Тогда как ?<hr></blockquote>

недобрый Вы, Wanderer [img:45b8d2a598]images/smiles/icon_sad.gif[/img:45b8d2a598] [img:45b8d2a598]images/smiles/icon_mad.gif[/img:45b8d2a598] [img:45b8d2a598]images/smiles/icon_wink.gif[/img:45b8d2a598]

XOR!

[ 27-12-2001: Message edited by: Drom ]

sttranik · Post by **sttranik** » 28 Dec 2001 03:58

<blockquote>quote:<hr>Originally posted by wanderer:
Для математика сойдет вполне [img:06aa4e0c2d]images/smiles/icon_smile.gif[/img:06aa4e0c2d] И действительно, просто и красиво.

Теперь для программистов: предположим, что мы используем такой тип целых чисел, что любая операция сложения или вычитания может вызвать переполнение [img:06aa4e0c2d]images/smiles/icon_sad.gif[/img:06aa4e0c2d]

Тогда как ?<hr></blockquote>
сложение в поле ? то что по программистки называется wrap around ?

теперь давайте усложним задачу. скажем что во втором массиве меньше не на одно а на два числа. как найти эти два числа?

PS. Между прочим мне эту задачу задавали на интервью [img:06aa4e0c2d]images/smiles/icon_smile.gif[/img:06aa4e0c2d]

Drom · Post by **Drom** » 28 Dec 2001 04:36

<blockquote>quote:<hr>Originally posted by sttranik:

сложение в поле ? то что по программистки называется wrap around ?<hr></blockquote>

а по-математитски wrap around это сложение по модулю? то есть просто отбрасывание старших знаков? для одного числа работает.
для 2х нет (как и XOR).

<blockquote>quote:<hr>теперь давайте усложним задачу. скажем что во втором массиве меньше не на одно а на два числа. как найти эти два числа?

PS. Между прочим мне эту задачу задавали на интервью [img:71e9c27f93]images/smiles/icon_smile.gif[/img:71e9c27f93] <hr></blockquote>

на интервю - если времени на подумать не очень много - я бы пошел по пути Чапаева - записать массив в hashtable (quicksort's complexity) со значениями чисел в качестве ключей, и количеством чисел в value - от первого массива с плюсом (+1), от второго с минусом (-1), при value=0 удалять совсем. оставшиеся после операции 1-2 ключа в таблице - искомые числа.

а вот если есть время подумать... тогда... [img:71e9c27f93]images/smiles/icon_sad.gif[/img:71e9c27f93]

[b:71e9c27f93]added:[/b:71e9c27f93]
все, sorry, крыша едет. уже перестал понимать, что такое сложение в поле. /напевая/ раскинулось поле по модулю пять, вокруг интегралы стояли...

[ 27-12-2001: Message edited by: Drom ]

wanderer · Post by **wanderer** » 28 Dec 2001 05:24

<blockquote>quote:<hr>Originally posted by Kisena:
А сравнивать можно? Насколько мы помним, сравнение двух чисел производится путем сравнения их разницы с нулем. Или теперь так не делают? Или никогда так не делали?<hr></blockquote>

Не-ааа .... не делали [img:29cbd278ca]images/smiles/icon_sad.gif[/img:29cbd278ca]

Sttranik, может как то можно найти и два числа. Но в моей задачи простое решение возможно лишь потому что число одно.

[ 27-12-2001: Message edited by: wanderer ]

Drom · Post by **Drom** » 28 Dec 2001 05:39

<blockquote>quote:<hr>Originally posted by wanderer:
Не-ааа .... не делали [img:f7d6e34eee]images/smiles/icon_sad.gif[/img:f7d6e34eee]

Sttranik, может как то можно найти и два числа. Но в моей задачи простое решение возможно лишь потому что число одно.<hr></blockquote>

может и делали - вроде бы SUB оставлял те же флаги, что и CMP - но это как-то не очень существенно.

простое (в смысле линейной сложности) решение должно быть! я в это верю, но уже засыпаю.
сумма чисел и сумма их квадратов должны содержать всю необходимую информацию для восстановления выброшенных (даже по модулю имени wrap around'а).
если проснусь - попробую дорешить.

D.

Andy77 · Post by **Andy77** » 28 Dec 2001 17:42

<blockquote>quote:<hr>Originally posted by Drom:
сумма чисел и сумма их квадратов должны содержать всю необходимую информацию для восстановления выброшенных (даже по модулю имени wrap around'а).
если проснусь - попробую дорешить.
D.<hr></blockquote>

странно, что Вы сразу не написали ответ [img:38049b6c2c]images/smiles/icon_smile.gif[/img:38049b6c2c]

пусть
s1 = sum(X) - sum(Y) == s1
s2 = sum(X*X) - sum(Y*Y) == s2 // разница сумм квадратов

тогда
a + b == s1
a^2 + b^2 == s2

квадратное уравнение...

wanderer · Post by **wanderer** » 28 Dec 2001 19:20

<blockquote>quote:<hr>Originally posted by Drom:


недобрый Вы, Wanderer [img:19fbf04f84]images/smiles/icon_sad.gif[/img:19fbf04f84] [img:19fbf04f84]images/smiles/icon_mad.gif[/img:19fbf04f84] [img:19fbf04f84]images/smiles/icon_wink.gif[/img:19fbf04f84]

XOR!

[ 27-12-2001: Message edited by: Drom ]<hr></blockquote>

Drom, так как же насчет XOR ? Жалко, такая идея ... и заброшена ...

Drom · Post by **Drom** » 29 Dec 2001 00:24

<blockquote>quote:<hr>Originally posted by wanderer:


Drom, так как же насчет XOR ? Жалко, такая идея ... и заброшена ...<hr></blockquote>

ага. XOR это не идея, XOR это решение: то ыесть в предложенном решении со сложением и вычитанием заменяем и то и другое на XOR.
другими словами XOR'им все числа из обоих массивов, результат - потерянное число.

Drom · Post by **Drom** » 29 Dec 2001 00:34

<blockquote>quote:<hr>Originally posted by Andy77:


странно, что Вы сразу не написали ответ [img:67554779f7]images/smiles/icon_smile.gif[/img:67554779f7]

пусть
s1 = sum(X) - sum(Y) == s1
s2 = sum(X*X) - sum(Y*Y) == s2 // разница сумм квадратов

тогда
a + b == s1
a^2 + b^2 == s2

квадратное уравнение...<hr></blockquote>

да, именно так [img:67554779f7]images/smiles/icon_wink.gif[/img:67554779f7] я только попытался ограничится, допустим, одним байтом для исходных чисел и сумм, потом получить что-то из того, что числа целые и на этом уснул. будет время - повожусь побольше.
впрочем у меня появилось подозрение, что мы занимаемся Error Correction Code'ами и таких "восстанавливающих"алгоритмов можно найти в сети.

AK70 · Post by **AK70** » 29 Dec 2001 01:09

<blockquote>quote:<hr>Originally posted by wanderer:
Дан массив X[N] несортированных целых чисел. Второй массив Y[N-1] получен удалением из X одного числа. Определить удаленное число (но не обязательно его положение в массиве X) наибыстрым образом.

Подсказка - как это можно было бы ЗАПРОГРАММИРОВАТЬ?

[ 27-12-2001: Message edited by: wanderer ]<hr></blockquote>

sort them both first, then it's easy. it'll be 2N(logN+1)

Andy77 · Post by **Andy77** » 29 Dec 2001 09:14

<blockquote>quote:<hr>Originally posted by wanderer:


Drom, так как же насчет XOR ? Жалко, такая идея ... и заброшена ...<hr></blockquote>

так вроде бы очевидно [img:9f2d5bf5d7]images/smiles/icon_smile.gif[/img:9f2d5bf5d7]

Andy77 · Post by **Andy77** » 29 Dec 2001 19:29

<blockquote>quote:<hr>Originally posted by AK70:
sort them both first, then it's easy. it'll be 2N(logN+1)<hr></blockquote>

АК70, Вы всегда так пишите в топики - не прочитав его сначала? [img:9a3e6081e0]images/smiles/icon_smile.gif[/img:9a3e6081e0] кроме того, сложность данного алгоритма - N*log(N)... 2N(logN+1) - это что? кол-во операций? каких? [img:9a3e6081e0]images/smiles/icon_smile.gif[/img:9a3e6081e0]

- занудствую [img:9a3e6081e0]images/smiles/icon_smile.gif[/img:9a3e6081e0]

[ 29-12-2001: Message edited by: Andy77 ]