Другие языки программирования и технологии

Помогите с алгоритмом!

В массиве 2N+1 элементов, из них у N элементов есть пара (равный элемент). Найти единственный непарный элемент с ограничением алгоритма по времени O(N) и по памяти O(1). Прочитала, что надо применять XOR, но неясно, как он будет здесь работать( Помогите, пожалуйста, написать алгоритм (код еобязателен, можно просто шаги).
ДТ
Динис Тулаев
101
Все просто до безобразия. Накапливаем в цикле XOR всех элементов. В результате все парные элементы взаимно нейтрализуются, накопленное значение равно непарному. Готово.
Время O(N) - один проход по циклу. Память O(1) - параметр цикла и аккумулятор.
SM
Saidjon Muratbekov
99 883
Лучший ответ
Примерно так, для массива при N=4:

#include<iostream>
using namespace std;
void main()
{
const int N=4;
int i, A[ 2*N + 1 ]={3,2,1,1,2,5,3,4,4};
for(i=0;i < 2*N;i++)
if((A[ i <= 0 ] ^ A[ 1 + (i <= 1)] ^ A[ 2 + (i <= 2)] ^ A[ 3 + (i <= 3)]) == (A[ 4 + (i <= 4)] ^ A[5 + (i <= 5)] ^ A[ 6 + (i <= 6)] ^ A[ 7 + (i <= 7)])) break;
cout << "Непарный элемент имеет номер i=" << i << endl;
}

Нужна одна ячейка для переменной цикла, хотя можно и без неё обойтись, если сделать программу линейной (без цикла)
Результат может найтись сразу при первом сравнении или после всех 2*N сравнений
В среднем это как раз будет равно уровню сложности в N сравнений!
Виктор Кочнев
Виктор Кочнев
76 473
Интересная задача. Трудная.
Могу попробовать помочь, но на ночь это не очень эффективно. Пишите на почту, если дело не срочное, завтра обдумаем.
Первое, что напрашивается, это отсортировать массив, так как без сортировки вряд ли удастся написать алгоритм с заданными требованиями. Сложность по памяти O(1) имеется в виду, что разрешается держать в памяти только один элемент массива?
На каком языке собираетесь писать программу?
Денис Харьковский
Денис Харьковский
14 410

Похожие вопросы