Дан массив целых чисел, в котором все числа встречаются ровно 2 раза, кроме одного, которое входит только 1 раз. Нужно за конечное число проходов O(1) массива и используя дополнительной памяти не более O(1) найти его.

хм... ню решение то простое подхватываем элемент и бежим по массиву если есть тоды прерываем берем следующий и снова бежим - если не находим тоды искомое...
что нить поизощреннее на ум не приходит - понедяльник

Выгрузить в ТЗ, добавить числовую колонку, заполнить единичками, свернуть. просуммировав. Найти строку, где значение в колонке = 1

массив можно отсортировать, затем сравнивать рядом стоящие элементы. тогда за один проход

(0) Перексорим весь массив - получим искомое.

(3) такой сортировки нету

(5) в смысле - в один проход

(0) "за конечное число проходов"...
А за бесконечное число проходов это как?!
:)))

(1)(2)(3)(4) не обойтись за О(1)
(7) можешь конечное убрать, если смущает

(2) и ТЗ требует памяти больше чем О(1)

Что-то я не порйму, как можно произвольный массив пробежать за константное время...

(8) Что значит O(1)
Скока точно в граммах © Не помню, реклама какая-то...

(10) не за константное время, а число проходов константа

(11) не зависит от длины входящего массива в данном случае

(12) тады (1)...

(14) Неа.

(15) why?

(16) Количество циклов в (1) зависит от длинны массива

(14) общее число сдвигов по массиву должно быть O(N), а там итеаций O(N), а сдвигов O(N^2)

+(18) а там проходов O(N)

(18) Вы выражайтесь русскими словами пожалуйста.

(20) поправился в (19)

(4) Как это? Находится за 1 (Один) проход - благодаря свойству x XOR x = 0.

(22)->(8)

(22) чего?

(22) Что с чем ксорить будем?

Массив надо отсортировать сначало

Потом сравнивать i элемент с i+1 элементом в i/2-1 цикле

(26) Сортировка уже выходит за ограничения...

(25) Всё со всем.

R = 0;
for (int i=0; i<N; i++)
  R ^= A[i];

+(29) XOR - ассоциативен и коммутативен, x^x=0.
Числа встречаются по 2 раза, кроме одного.

(29) красавчик

(30) Тоесть:

((12 xor 25) xor (12)) xor(25) =0 ?

(32) Не поверишь - но так и есть.

Теперь 2-я часть: таких числа (встречающихся один раз) - два

то (34)
если осортировать то хоть Все не повторяющиеся.

(35) отсортировать очевидно нельзя

(36)
что такое конечное число проходов O(1)
1 проход ?

Бежим по массиву и добавляем числа в другой массив. При добавлении проверяем содержится ли уже это число в массиве, если содержится то не добавляем и удаляем. Как то так наверное.

(37) число проходов не зависит от длины массива
(38) нельзя пользоваться памятью, размер которой зависит от размера массива

(39) А сколько памяти можно использовать?

(40) в (38) норм с памятью, там число проходов больше О(1)

(40) O(1) - независимое от размера исходного массива количество

(41) с памятью тоже не нормально

(42) ню-ню

(44) это ты от безисходности? я сам решения не знаю

Стотыщмильоновгуглионов байт тоже не зависит от исходного массива ибо такой массив не будет заполнен за время жизни вселенной. Сколько вешать в граммах (байтах)?

(46) не надо крайностей, вы слишком уж взъелись к условиям

Сам подумай. Мы ведь не ограничиваем память на хранение одного числа, значит такая программа всегда будет зависеть от размера массива.

(4) зачет!
ппц ветка, сразу видно, кто 1С-ник, а кто программист

(48) например если нужно подсчитать сумму,максимум и среднее массива, то число дополнительной памяти не зависит от размера массива

Есть такой класс математических задач. Я придумал условие, вы попробуйте её решить, а дополнительные условия, я вам потом расскажу, когда вы себе мозг сломаете.
Либо мы решаем теоретическую задачу, тогда (48) и задача решения не имеет, либо практическую и размер целого числа зависит от процессора, тогда (4). Как то так наверное.

(51) есть такой тип людей, которые понимают условие задачи сразу, а есть, которые нет

(51) ну решишь ты мою задачу или свою, я медаль тебе все равно не дам, это же форум, а не конкурс

(51) d cfl

(52) Я отучился понимать условия задач сразу, потому как озвученные фантазии пользователей никогда не совпадают с ожидаемым ими результатом. Поэтому долблю их по голове до тех пор, пока они сами не поймут чего же они хотят. Сильно экономит время на программирование.

(54) А по теме? Сам то задачу решил? Поделись решением.

Решение через ранжирование для 1 незадвоенного  элемента


1) порбегаемся по таблице,  получаем максимум - минимум

2) создаем таблицу ранжирования (таблицу пападаний интервал)


3) заполняем таблицу
4) ищем в таблице поле  с нечётным количеством

меняем максимум и минимум

повторяем пункты   3) и 4)

пока максимум <> минимум

(57) но алгоритм не удовлетворяет условиям

(58)
Каким ?

(34) Если два незвестных в массиве Ai это a и b, то сначала получаем c = a xor b. Потом надо над всем массивом сделать некую операцию F (Ai) = Bi (еще не знаю какую). Потом над массивом Bi снова делаем xor.
На выходе получаем два уравнения, которые по идее должны решиться
с = a xor b
d = F(a) xor F(b)

(59) число проходов не зависит от размера массива? количество памяти в доп. таблице не зависит от размера массива?

даже юзая ксор число проходов будет зависить от количества элементов массива

(61)
Число проходов зависит от размера таблицы статистики

(62) число проходов - 1

(63) ничего не понял

(64)там цикл один ... а ротаций (читай число проходов) будет именно количество элементов массива

(66) с чего я должен это так считать? проход, это проход, а число итераций действительно O(N)

(67)ну я думал ты как минимум с программированием связан

(68) а при чем тут это?

(69)открой любой учебник по информатики ... за самые основы программирования и почитай ....

Каждый "проход" цикла называется итерацией.

В отличие от цикла while, этот цикл проверяет значение выражения не до , а после каждого прохода (итерации).

(70) еще один буквоед, написано же было в (0) "количество проходов О(1)"

+(70) ошибся, допускаю, условие в (0)

то (65)
N кол-во строк в таблице статистики
тогда  количество проходв <=  log N(максимум - минимум) + 1(первый проход)
и не зависит от размера исходного массива

(73) ну ты же сам написал "log N"

(74)
Согласен.
Это не "конечное число проходов"

(45) да затупил, вместо O(1),про O(n) подумал
вариант есть с ушами - блочная сортировка+проход по блокам (не зависит от длинны входной последовательности)

(34), +(60) в общем решение для двух различных чисел в массиве такое:
1)>Ксорим весь массив A[i], получаем c = X xor Y, где X и Y - искомые числа.
2) По условию c <> 0, смотрим двоичную запись и берем старший значащий бит =1. Пусть он стоит на k месте. Берем  M = 2^k.
3)Заметим, что
либо
X and M = 0 ; Y and M = М
либо
X and M = М ; Y and M = 0.

4) Преобразуем весь массив B[i] = (A[i] and M)/M * A[i].
тогда Xor массива B[i]  в силу заметки 3) будет равен или X или Y, т.к. одно из них в результате преобразования останется неизменным, а другое обнулится

(77) 4 пункт не понял сходу

(77) в принципе, доп память ненужна, достаточно 2 прохода

(78) во что превратятся другие числа - не важно. Их было по 2 шт., и результатов тоже будет по 2 шт, на конечный xor ини не повлияют.
Важно, что один из X или Y просто обнулиться, а другой нет

(78) Это решение подходит, или нужно другое?
Есть другое, черз нахождение среднего значения, подсчет количества элементов больше (и меньше его), отбора той части в которой находится единственное, и т.д.
Сложность алгоритма - N+N/2+N/4...=2N, то есть О(N)

(80)(81) надо проверить

(82) А чего проверять? и так понятно что отксорить даст искомое, и мой вариант тоже даст искомое. И в обоих случаях сложность О(N)

(81) в том то и дело, что "и т.д." (0) же хочет, что бы количество проходов не зависило от N

Кста, в (0) условие про доп память - лишнее.
Как можно использовать доп памяти больше, чем O(N), за количество операций, не более чем O(N)?

+(85) млин. Там как раз операций O(N), а памяти O(1).

(84) количество проходов массива, а сложность прохода одного прохода - О(N)
соответственно алгоритм с такой сложностью можно считать алгоримом за конечное число проходов.

(87) а количество доп памяти сколько потребуется?

(88) Максимум N элементов, в среднем N/2

(89) а в условии О(1)

(+89) Сначала перебрасываем из начального массива в дополнительный, потом обратно. И т.д.

(90) Ну тогда только ксорить.

Есть еще вариант - воспользоваться куском квиксорта находящим медиану...

(77) въехал. круто! респект, если сам!
только я бы по другому описал!
пусть искомые X и Y
1)первый проход ксорим все элементы получаем Z = Х^Y
2)Получаем младший бит U = ((Z ^ (Z-1)) + 1) / 2 (вахаха, люблю побитовые операции)
3)второй проход ксорим только те элементы, которые (A[i] & U) != 0. Получаем X!
4)Y = X ^ Z

(94) Ничего не понял. XOR всего массива в один проход даст искомый элемент.

Х=0;
Для а=1 по N цикл
Х=Х XOR Масс[а]
Конеццикла;
сообщить(X) - искомый элемент.

(95) - мы решаем с двумя неизвестными, т.е. задачу (34)

(96) Понял.

(субьективно) Забавное наблюдение. В этой ветке мне показалось, что персонажи с латинскими никами более подкованы в области общего программирования, нежели персы с русскими никами. В частности, фаворитами задач (0) и (34) являются Rie и Asirius. Случайность или закономерность? Может, это результат привычки давать переменным латинские имена? :) не бейте палками :)

(99) в 1 строку написал бы: "у меня ник латиницей, значит я тоже крутой"

сотня типа

Запросом.

(77)
На самом деле
Xor массива B[i]  в силу заметки 3) будет равен M, т.к. одно из них в результате преобразования станет М, а другое обнулится

+(102)
Или я что-то с преобразованием недопонял?

(103) все так
B[i] составлен только из числел, имеющих один конкретный бит; остальные занулены. среди них будет либо X либо Y, и какое-то количество пар.

мне нравится в ваши рассуждениях пунктик "возьмем первый ненулевой старший/младший бит". ага, прям руками и возьмем. но это мелочи.
усложним задачу: условия (0), в языке нет битовых операций

+(105) Побитовый XOR на языке 1С

(105) почему нет?
а с побитовыми операциями младший бит (точнее число только с младшим битом) добывается несложно

(106) я имел ввиду - решить эту задачу без битовых операций вообще

(108) а, тфу, спросоня не могу прочитать

(105) +, -, *, /, % - есть?
Значит, и побитовые есть.

вот так это решается на python:

b=[a[x] for x in xrange(0,len(a)) if a[x] not in a[:x]+a[x+1:]]

(111) И какова сложность этого решения? Соответствует ли она условиям в (0)?

(112) сложность этого решения - в одну строчку

(113) По времени и по памяти.

(113)+ если серьезно, то с точки зрения _языка_ тут всего 1 цикл. и дополнительная память не выделяется, поскольку xrange() - ленивый генератор. ну а как в трасляторе реализовано взятие слайсов, сложение массивов, и оператор in - дело десятое

(115) Ленивый генератор с этой точки зрения просто "заменяет" расход памяти расходом времени.
При наиболее эффективной реализации в трансляторе _этого генератора_ (без глобальной оптимизации, которую до сих пор мало кто делает) он доблестно потратит len(а) времени на каждом шаге.

запустил на массиве 2 млн.-1 элементов (1..1000000..1)
отъел ~50 мегов памяти, атомный проц где-то на 80%, считает уже минут 5... :)
(python 2.5.1)

(116) я же говорю - с точки зрения _языка_.
как это реализовано в трансляторе - дело десятое, иначе и для C++ надо будет залезть внутрь какого-нибудь gcc и разбираться, как же там "наоптимизированы" операции работы со списками.
вообще, идеологически, задача в (0) решается совсем просто:
определяем _язык_, в котором задана такая операция над массивом. все - никаких циклов.

(118) Секция - "Математика и алгоритмы". При чём тут язык?
Алгоритмическая сложность от языка не зависит. Даже если в языке есть метод Sort, сортировку он быстрее чем за N log N не сделает.

(119) при том, что нельзя пытаться мыслить абстрактно, при этом не выходя за рамки парадигмы.

идите работать

(120) Кто запретил? Надо мыслить абстрактно, надо оценивать сложность алгоритмов - хотя бы для разработки эффективно работающих конструкций высокого уровня. И представлять себе, во что они выливаются.
Ты же при работе с 1С - оцениваешь, какая конструкция будет эффективнее? Или тоже, мысля в рамках парадигмы, использует полный перебор справочника с проверкой условий вместо запроса с условием на индексированный реквизит?

(122) 1С ты вообще приплел зря.
вот вы, решая задачу (0) почему-то решили, что взятие элемента массива по индексу имеет скажем так "единичную мощность". с точки зрения языка - это так, с точки зрения реализации - нет. то же самое относится к любой операции. опять же с точки зрения реализации будет важно, какова "природа" этих целых чисел и определены ли над ними битовые операции. я привел пример на питоне, который формально полностью удовлетворяет условию задачи, причем он решает более общую задачу: поиск всех одиночных элементов массива. Кроме того, в том же питоне есть встроенная функция filter(). Если переписать эту строку с ее помощью, то _формально_ вообще ни одного цикла не будет.

(123) Ты условия задачи внимательно прочитал? Там о "единичной мощности" - ни слова. Сказано лишь - за константное число проходов.
В _других_ задачах - могут быть и другие условия. Но это будут уже _другие_ задачи. С, возможно, _другими_ решениями.

(123) Сложность алгоритмов это наука. Сложность не зависит от языка и реализации. Зависит только от алгоритма.

Не знаю, было или нет, но предложение с xor-ами натолкнуло вот на такую мысль:
int i;
int S = 0;
bool flag = true;
for (i = 0; i<= N-1; i++) {
 if (flag)
   S += array[i];
 else
   S -= array[i];
 flag = !flag;
}
Ну а дальше смотрим на знак S. Если отрицательное, то ответ -S, если положительно, то это и есть искомый ответ.

(126) уверен, что одинаковые не будут с одним знаком?

(127) Мдя, обломс...

(123) Как бы то ни было, все это будет выполнять не язык, а процессор. Так вот все, известные мне, процессоры умеют xor, а filter() не умет ни один. "Взятие элемента массива по индексу" - всего-лишь пример, чтобы объяснить суть *алгоритма* автору задачи. А там уж автор пуст сам решает как перебирать элементы своего массива. Вы же предлагаете не общий алгоритм (который будет выполнять процессор), а конкретное решение на конкретном языке, что не соответствует условию задачи (0).

(77) (94) А зачем так сложно?
U = ((Z ^ (Z-1)) + 1) / 2 - ну нефига себе...
Если искомые х1 и х2, то:
1) Как в (29) находим r = x1 xor x2;
2) Делаем проверку на каждый элемент массива (a[i]):
 если (r and a[i]) равно a[i], то a[i] есть х1,
 либо: если (r or a[i]) равно r, то a[i] есь х1;
3) x2 = r xor x1;
Кажется так... о.О

(129) То есть, при искомых значениях 1100 и 0001 мы получили r=1101. Теперь перебирая массив мы наткнулись на число 1001 - проверка "если (r and a[i]) равно a[i], то a[i] есть х1" - будет им успешно пройдена.

(130) Ну да :) С просони не сообразил.