[задачка] Найти непарные числа

Какую-либо структуру данных в памяти/на диске нельзя создавать.

unsigned int arr[] = { 1, 1, 14, 2, 3, 4, 5, 3, 2, 4, 14, 7, 8, 5, 8, 9, 11, 10, 10, 11, 12, 12 };

/0
Ограничения задачи слишком расплывчаты.

Ну это тестовый массив. Не буду же я генерить несколько терабайт тестовых данных.

Бей файл на пополам и ксорируй куски отдельно. Если один =0, забудь про него и бей второй пополам, и т.д. Если оба ксора не =!0 - это и есть искомые числа.

s/не =!0/=!0/ 

:-)

а нет, неправильно.

В один регистр сумму по модулю 2, как обычно. Во второй - простую арифметическую сумму. Потом придется решить небольшую систему уравнений.

Пусть a и b - искомые элементы. Посчитаем a xor b. Он очевидно не ноль, иначе a=b. Пусть i - ненулевая позиция a xor b. Заменим все числа, у которых в i-й позиции единица на 0xffffffff. Остальные оставим как прежде. Снова посчитаем xor. Из этих двух xor'ов можно восстановить a и b, что оставляется автору в качестве упражнения.

Второй вопрос я решить не смог: что делать, если непарных чисел два?

Храним предыдущий результат xor (т.е. до нахождения искомого числа), после нахождения искомого, исключаем это действие и продолжаем дальше. ИМХО, для этого удобней использовать while (i < arr_size), вместо for() и инкрементации делать внутри цикла, ибо придется использовать инкрементацию на шаг вперед от текущего i.

1. Любой разряд, где общий xor даёт единицу, считаем, например, равным 0.
2. Следующие разряды по одному подбираем так, чтобы количество чисел, имеющих подбираемое с подобранным в соответствующих разрядах, было нечётное.

А кто сказал что парные числа ПОДРЯД идут ? :)

Нельзя структурку, но 64 бита можно. Это они злобно. Если иметь 2 * 64 *64 бит, то задание становится тривиальным и однопроходным (скорее всего это быстрее чем читать 2 раза, хотя сложность алгоритма существенно выше). Можно собирать xor по тем у кого в определенной позиции 0 в одно место, а тем у кого 1 в другое. Итого 128 мест (кил). Можно, конечно, и общий xor хотя он нафиг не нужен. Далее в одной из 64 пар обнаруживаем оба числа.

Хреново описал, лучше бы: с помощью не 0 в xor определяем индикатор (разбивает на подмножества пар, причем непарные в разных), сразу видно, что сводится к 1 случаю и не надо плясать 64 раза:

pairs = [1,1,14,2,3,4,5,3,2,4,14,7,8,5,8,9,11,10,10,11,12,12]

ind, xor = 1, reduce(lambda x,y: x^y, pairs)
while not (xor & ind):
    ind *= 2

res = 0
for e in pairs:
    if e & ind: res ^= e

print res, res ^ xor

Браво.

Нельзя структурку, но 64 бита можно.

Возможно имеется ввиду, что нельзя динамически выделять память.

есть файл на несколько терабайт, на каждой строке 64битный int,

текстом или бинарно, little endian, big endian? :)

Это на чем? Сходу не понял.

А какая разница, какой там endiannes? Текст/бинарно в данном случае тоже похер, учитывая 64битность (диапазон) и размер файлов.

Тривиальный пример:
1+1+1+4=7 1^1^1^4=5
1+1+0+5=7 1^1^0^5=5
показывает, что с решением системы уравнений имеем некоторые проблемы.
Впрочем ничто не мешает использовать другие операции.

Это на чем? Сходу не понял.

Питон же.

Может быть достаточно и одного прохода, кстати:

arr=[1,1,14,2,3,4,5,3,2,4,14,7,8,5,8,9,11,10,10,11,12,12]

[ax,r]=reduce(lambda n,e: [n[0]^e,n[1]^(e&-(len(bin(e).split('1'))&1))],arr,[0,0])

if r in [0,ax]: r=reduce(lambda n,e: [n[0]^(e&-(e&n[1]>0)),n[1]],arr,[0,2**len(bin(ax).split('1')[-1])])[0]

print r,r^ax

Малочитабельно ведь. Питон в фун. стиле смотрится не очень, уж лучше хаскель.

А если так?:

arr=[1,1,14,2,3,4,5,3,2,4,14,7,8,5,8,9,11,10,10,11,12,12]

ax=reduce(lambda n,e: n^e,arr,0)
m=2**len(bin(ax).split('1')[-1])
r=reduce(lambda n,e: n^(e&-(e&m>0)),arr,0)

print r,r^ax

Получше. ,0 - вероятно лишний здесь (в первом reduce). Ну и &-(e&m>0) таки хак (по-крайней мере мне понадобилось секунд 20 чтобы распарсить).

А поясни сущность хака, пожалуйста.

А поясни сущность хака, пожалуйста.

Получается либо n^e, либо n (один из способов избежать if в лямбде). Используется: n & -1 = n & 0b111... = n.

Точнее, во втором предложении s/n/e/.

Вот что ты человека сбиваешь, насколько я понял, все-таки !=0

не 0, а '0'

Вот так:

arr=[1,1,14,2,3,4,5,3,2,4,14,7,8,5,8,9,11,10,10,11,12,12]

es,r,ax=64,0,0

for e in arr:
    ax,b=ax^e,bin(e)[2:]
    for n in xrange(len(b)):
	if b[n]>'0': r^=e*(2**((n+es-len(b))*es))

r=(r/2**(len(bin(r).split('1')[-1])/es*es))&(2**es-1)

print r,r^ax