не знаю, насколько тут приветствуются подобные задачки, но...

Есть массив из N чисел.

1. Он заполняется числами так:
    - числа эти лежат в пределах [1; N]
    - никогда не повторяются
    - в случайном порядке
(к примеру для N == 5 массив может иметь вид {2, 5, 3, 1, 4})

2. Одно (любое) из чисел меняется на N + 1.
(для преведенного выше примера это может быть {2, 5, 3, 6, 4})

3. Программе на вход подается полученный массив ({2, 5, 3, 6, 4}). Она должна определить, какое число заменили. Как можно быстрее.

Ответом должен быть код на С++, реализующий "поиск".

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

Alek86, это в "Интересные задачи по программированию", имхо.

да? не знал, что есть 
извиняюсь

не понял в чем подвох...
вариант
недостаточно быстр?

для  {2, 5, 3, 6, 4} твоя программа выведет 3, а не 1, как требовалось

нужно не индекс, а ЧИСЛО определить 

Alek86, 

итого O(n) + O(n) = 2 * O(n) ~ O(n)

идея засчитана.
может кто ЕЩЕ лучше найдет?

а... я подумал, что нужно индекс определить

итого O(n)

Добавлено через 4 минуты и 38 секунд
думаю, оптимальный вариант

Это сообщение отредактировал(а) MAKCim - 11.11.2007, 13:08

я ж говорил, несложная
быстро нашел

Не знаю, лучше или нет, но тоже вариант.   

ёпрст
проверил, работает. но КАК, даже разбираться не хочется...


если хотел как можно злостней решение придумать, ты цели достиг ;)

Dov, вариант MAKCim, имхо, быстрей. Скорость выполнения XOR равна скорости выполнения сложения, а у тебя арифметических операций в 3 раза больше в каждой итерации цикла.
Хотя, для малых массивов твой вариант быстрее будет за счет отстуствия умножения (деление не считаю - любой порядочный компилятор обязан заменить его на сдвиг).

Это сообщение отредактировал(а) bsa - 11.11.2007, 19:40

Alek86, ты чего?   Это самое простое решение, которое пришло мне в голову.    Где-то здесь, на форуме(и не только на этом)  есть похожая задача, где нужно в массиве, состоящем из нескольких пар одинаковых чисел и одного непарного, например: {1,3,4,2,3,5,2,1,4}, найти это самое непарное число.  Так проще всего она решается именно этим способом. Проходим ХОR`ом весь массив и на выходе получаем искомое число. Что я и сделал.   


bsa, вполне возможно. Я хронометраж не делал.   

bsa, а для больших массивов(на пару миллионов) у меня не  будет такой траблы, например:

Догадываешься?   

Вроде задача простая на знание арифметической прогрессии.

Формул к сожалению не помню (учился давно, если надо могу вспомнить)

1. Бежишь по массиву, считаешь сумму, и вычисляешь кол-во элементов в массиве.
2. Вычисляешь сумму арифметической прогрессии
3. Вычитаешь из суммы, полученной в первом пунке сумму арифм. прогрессии
и еще вычитаешь N (кол-во элементов) - это и будет искомое число.

Скорость вычисления O(N)

Это сообщение отредактировал(а) Nat - 13.11.2007, 08:38

Nat, 
возьми массив {4, 2, 3}
у тебя будет вывод 7
а надо 1
+ для суммы арифметической прогрессии есть формула и не за чем вычислять ее в цикле

Пардон, неправильно прочел условия :(

Это сообщение отредактировал(а) xvr - 12.11.2007, 15:28

Не проверял, но должно работать

Это сообщение отредактировал(а) DKroshkin - 12.11.2007, 18:38

вроде, верно
жаль, ты не первый 

Sorry, исправила :-[ Теперь должно правильно считать.

Ага обидно. прочитал всю ветку и нашел формулу для вычисления арифм. прогрессии.
))