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

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 ]

Dmitry67 · Post by **Dmitry67** » 30 Dec 2001 05:26

А я вначале подумал что число удаленное - "remote", а не "removed"

AK70 · Post by **AK70** » 03 Jan 2002 16:31

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


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

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

[ 29-12-2001: Message edited by: Andy77 ]<hr></blockquote>

ok, it's O(N*log2(N))

so, what's a prob with my perfect solution?

I guess there could be faster implementation. but, u have to spend time thinking about it. while my solution is so stupid that it will take no time to implement it.

Andy77 · Post by **Andy77** » 03 Jan 2002 19:23

<blockquote>quote:<hr>Originally posted by AK70:
I guess there could be faster implementation. but, u have to spend time thinking about it. while my solution is so stupid that it will take no time to implement it.<hr></blockquote>

AK70, опять не прочитали топик? [img:f7ee8bafa6]images/smiles/icon_smile.gif[/img:f7ee8bafa6] в нём не только было предложено Ваше решение, но и найдено решение с линейной сложностью, посмотрите сами [img:f7ee8bafa6]images/smiles/icon_smile.gif[/img:f7ee8bafa6]

Siberian Cableman · Post by **Siberian Cableman** » 03 Jan 2002 20:27

To Drom
/напевая/ раскинулось поле по модулю пять, вокруг интегралы стояли...

Drom, are you from MEI (Moscow Power Engineering Institute ) may be?
Song is very simular.

Drom · Post by **Drom** » 07 Jan 2002 23:10

<blockquote>quote:<hr>Originally posted by Siberian Cableman:
To Drom
/напевая/ раскинулось поле по модулю пять, вокруг интегралы стояли...

Drom, are you from MEI (Moscow Power Engineering Institute ) may be?
Song is very simular.<hr></blockquote>

nope, sorry. from MIPT if it matters. and heard this song if memory still serves me in Bashkiria kind of seven years ago - so guess the song is pretty inter-national/institutional/whateveral [img:b6967f622f]images/smiles/icon_wink.gif[/img:b6967f622f]