Вот идея решения за O (nw) времени, где w - размер машинного слова (обычно 64 или какая-то другая константа). Самым важным является подсчет количества пар, для которых будет установлен конкретный бит, и четность этого числа определяет, будет ли этот бит установлен в результате. Цель состоит в том, чтобы посчитать, что за O (n) время вместо O (n 2 ).
Найти самый правый бит результата проще всего. Подсчитайте, сколько из входных чисел имеет 0 в крайнем правом месте (т.е. сколько четных), и сколько там 1 (т.е. сколько нечетных). Число пар, сумма которых имеет 1 в крайнем правом месте, равно произведению этих двух отсчетов, поскольку пара должна иметь одно нечетное и одно четное число, чтобы ее сумма была нечетной. Результат имеет 1 в крайней правой позиции, если и только если этот продукт нечетный.
Найти второй правый бит результата немного сложнее. Мы можем проделать тот же трюк, подсчитав, сколько элементов имеет и не имеет 1, а затем взяв произведение этих подсчетов; но нам также нужно посчитать, сколько 1 бит переносится на второе место из сумм, где оба числа имели 1 на первом месте. К счастью, мы можем вычислить это, используя счет предыдущего этапа; это количество пар, определяемых формулой k * (k-1) / 2, где k - количество пар с 1 битом на предыдущем месте. Это можно добавить к продукту на этом этапе, чтобы определить, сколько 1 битов находится на втором месте.
Каждый этап занимает O (n) времени для подсчета элементов с 0 или 1 битом в соответствующем место. Повторяя этот процесс w раз, мы можем вычислить все w битов результата за O (nw) времени. Я оставлю фактическую реализацию этого вам.