За целый день ни одной задачи!
Простенькая и достаточно известная задача для разминки.

В массиве целых чисел каждое число имеет пару, т.е. встречается 2, 6, 8 ... раз. И только одно число не имеет пары. Пары не обязательно лежат рядом.

Как наиболее быстро найти это непарное число?

Привет, MichaelP!

MP>В массиве целых чисел каждое число имеет пару, т.е. встречается 2, 6, 8 ... раз. И только одно число не имеет пары. Пары не обязательно лежат рядом.
MP>Как наиболее быстро найти это непарное число?

Ха! Осенило! Вот что я придумал!

Надо их xor-ить все подряд! В итоге получим искомое число!

Chto schitat' prostim resheniem ??

Sorturuem MASSIV i delaem WHILE poka RAZNOST' nechetnogo i chetnogo NE RAVNA O. Iskomya raznitsa i est' to chislo....



Здравствуйте, MichaelP, Вы писали:

MP>За целый день ни одной задачи!
MP>Простенькая и достаточно известная задача для разминки.

MP>В массиве целых чисел каждое число имеет пару, т.е. встречается 2, 6, 8 ... раз. И только одно число не имеет пары. Пары не обязательно лежат рядом.

MP>Как наиболее быстро найти это непарное число?

Imelos' vvidu nechetnogoi chetnogo chelonov nachinay s 0-go... Po krainei mere eto proseh, chem tsikl po chlenam s podchetom povtorov...





Здравствуйте, nob113, Вы писали:

N>Chto schitat' prostim resheniem ??

N>Sorturuem MASSIV i delaem WHILE poka RAZNOST' nechetnogo i chetnogo NE RAVNA O. Iskomya raznitsa i est' to chislo....



N>Здравствуйте, MichaelP, Вы писали:

MP>За целый день ни одной задачи!
MP>Простенькая и достаточно известная задача для разминки.

MP>В массиве целых чисел каждое число имеет пару, т.е. встречается 2, 6, 8 ... раз. И только одно число не имеет пары. Пары не обязательно лежат рядом.

MP>Как наиболее быстро найти это непарное число?

Здравствуйте, Apapa, Вы писали:

A>Надо их xor-ить все подряд! В итоге получим искомое число!

Просьба, оцените этот ответ! А то у меня лимит на Apapa исчерпывается.

Здравствуйте, MichaelP, Вы писали:

MP>Просьба, оцените этот ответ! А то у меня лимит на Apapa исчерпывается.

Тем кто не понял. Надо оценить не иой ответ, а ответ Apapa.

Здравствуйте, MichaelP, Вы писали:

MP>Здравствуйте, MichaelP, Вы писали:

MP>Просьба, оцените этот ответ! А то у меня лимит на Apapa исчерпывается.

MP>Тем кто не понял. Надо оценить не иой ответ, а ответ Apapa.
ну промазал малость

Здравствуйте, Apapa, Вы писали:

A>Привет, MichaelP!

MP>В массиве целых чисел каждое число имеет пару, т.е. встречается 2, 6, 8 ... раз. И только одно число не имеет пары. Пары не обязательно лежат рядом.
MP>Как наиболее быстро найти это непарное число?

A>Ха! Осенило! Вот что я придумал!

A>Надо их xor-ить все подряд! В итоге получим искомое число!

Если под "найти" в условии задачи имелось в виду нахождение позиции числа в массиве, то придется истратить еще одно O(n) на поиск этой позиции. Асимптотически, разумеется, сложность не изменится...

Здравствуйте, Apapa, Вы писали:

A>Ха! Осенило! Вот что я придумал!

Забавно... Эту задачу дают первокурсникам и спрашивают на каждом втором собеседовании...