Это невозможно.
Пусть у нас есть массив, состоящий НЕ ЦЕЛИКОМ из нулей и содержащий хоть один ноль.
Возьмём любой ненулевой элемент a и про-XOR’им с ним все элементы массива.
Ноль переместился в другое место, а результаты нашей операции a[i] xor a[j] не изменились.
Получается, что первый массив неотличим от второго, и нули в них в разных местах.
Например: массив 0 1 2 3 неотличим от массива 1 0 3 2.
0 xor 1 = 1 … 1 xor 0 = 1
0 xor 2 = 2 … 1 xor 3 = 2
0 xor 3 = 3 … 1 xor 2 = 3
1 xor 2 = 3 … 0 xor 3 = 3
1 xor 3 = 2 … 0 xor 2 = 2
2 xor 3 = 1 … 3 xor 2 = 1
Ну а 0 xor 0, 1 xor 1, 2 xor 2 и 3 xor 3 всегда были нулями.
------------------
В версии с OR — берём a[0] or a[i], поддерживая AND этих сумм и подсчитывая, сколько раз этот самый AND среди наших сумм встречается.
1) Если числа, превышающие AND, встречаются столько раз, сколько [ну, подсчитайте, сколько чисел от 0 до N−1 будут иметь все эти биты] — отбросим наше 0-е число, а также проверенные числа, чья сумма НЕ совпадает с AND, и начнём сначала.
ПРИМЕР: 2 3 4 0 1
2 or 3 = 5, AND=5
2 or 4 = 6, AND=2 — бит 2 тут будут иметь только 2 и 3, отбрасываем 2, 3 и 4.
Если AND встречается 2k−1 раз (k — кол-во битов в AND), оставим ТОЛЬКО ЭТИ случаи и снова начнём сначала.
ПРИМЕР: 2 1 0 3
2 OR 1 = 3, AND=3
2 OR 0 = 2, AND=2
2k−1=1, и нам хватает одной встречи числа 2 — оставляем 2 и 0.
Остались три числа — действуем по стандартному алгоритму.
Осталось одно число — оно 0.
Остались два числа — одно 0, другое некий бит. Мы должны найти число, этого бита не имеющее. Снова проходим по результату предыдущего обхода, суммируя сначала с одним, потом с другим. Видим разницу — понятно, где 0, а где бит.
