Форум программистов [Powered by Invision Power Board]

Версия для печати темы
Нажмите сюда для просмотра этой темы в оригинальном формате

Форум программистов > Алгоритмы > Найти одинокое число

Автор: YuriT 23.4.2004, 01:41

есть массив... в массиве числа. известно что все числа в массиве кроме одного имеют пару. надо найти это одинокое число наименьшими затратами ресурсов (одним циклом - это обязательно)

1 3 5 2 3 1 5 ответ 2
111 111 111 111 24 26 26 24 7 ответ 7
5 13 13 5 5 6 6 ответ 5

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

Автор: sergejzr 23.4.2004, 02:07

XOR'аешь все числа и в конце выходит твоё число.

Если точно, как ты сказал (то есть действительно нечётное кол-во), то всё будет нормально.
Дело в том, что он возвратит 0 при чётном количестве(ВСЕ парные). И 0 если 0 "одинокий".

Цитата

#include "stdio.h"
int findTheOnlyElement(int massiv[], int count)
{
int res=massiv[0];
for(int i=1;i<count;i++)
{
res=res^massiv[i];
}
return res;
}
int main()
{
int massiv[]={3,5,3,2,15,4,5,2,4};
printf( "element: %i \n" ,findTheOnlyElement(massiv,9));
return 0;
}