Любите ли Вы Brainstorm так,

[menato]

как люблю его я.

Речь вовсе не о Латвийском коллективе. Сегодня Саша Куликов aka kirpich_spb предложил интересную задачку по алгоритмике

Comments

[burunduk1]

А условие можно?)

[menato]

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

[worlds_owner]

Это что, шутка? Просто посчитай сумму.

[menato]

Числа могут повторяться разное число раз, могут не встречаться. Просто есть одно ограничение на множество, откуда они берутся.

[worlds_owner]

Что тогда "повторяющийся элемент"?

[menato]

Не поверишь: тот, что встречается 2 раза :)

[worlds_owner]

Да блин! Я правильно понимаю что нам дали n + 1 чисел от 1 до n, не перестановку и просят в произвольном порядке вывести все элементы которые встречаются больше одного раза?

[menato]

Не все, а только одно и любое. Что читается не однозначно в условии?

[sammarize]

Я ну, я так понимаю, что если операции с числами за O(1), то log(n) можно считать константой - логично? Тогда я вроде умею за n*log(n).

[menato]

За n * log n мы тоже придумали каждый за минутку :) Но идея в том, что есть проц, который делает за константу, а вот если побитого, то уже log вылазит.