программизм: вот такая задачка образовалась

[yigal_s]

Дан массив из N элементнов. Ну, к примеру, integers
Делается копия этого массива, элементы в ней случайно перемешиваются, а 4 элемента просто выкидываются.
Теперь у нас имеется два массива - из N и N-4 элементов.
-----
Требуется - быстро найти значения удаленных четырёх элементов.

Upd: дополнительное условие - не аллоцировать дополнительных массивов.

Comments

Re: В лоб

[yigal_s]

Кстати, верно. Я, как часто со мной случается, позабыл упомянуть дополнительное условие - обойтись небольшой памятью.

Re: В лоб

[dimrub.livejournal.com]

Если бы не хватало одного числа, можно было бы сделать ксор всем числам, и получить на выходе недостающее. А так результатом будет ксор этих четырех чисел. Но точно так же мы можем узнать их сумму, произведение и, скажем, сумму квадратов. Дальше решаем систему уравнений, и находим их.

Re: В лоб

[igorbor.livejournal.com]

То есть Вы предполагаете, что обьем хеша будет меньше обьема массива? Это, по-моему, в общем случае неверно. А если обьем хеша мал, то цена поиска в нем будет не меньше, чем цена сортировки изначального массива.

Re: В лоб

[yigal_s]

Нет, конечно, я так не полагаю.
Объем кэша - это O(N). Я хотел услышать решение без кэша (вот только сразу позабыл упомянуть в условии требование экономии памяти)