Найдите количество специальных подмассивов, в которых побитовое исключающее ИЛИ первого и последнего элементов равно XOR всех остальных элементов в подмассиве
Учитывая массив целых чисел, найдите количество подмассивов длиной не менее 3, где побитовое исключающее ИЛИ первого и последнего элемента в подмассиве равно остальным элементам в подмассиве. Можете ли вы придумать решение лучше, чем O(N^2)
Я придумал решение O (n ^ 2), используя prefix_array. Мне было интересно, есть ли оптимальное решение, чем это, потому что мое решение не может пройти последние пару тестовых случаев.
Ответы 1
Если побитовое исключающее ИЛИ двух краевых элементов равно исключающему ИЛИ внутренних элементов, то исключающее ИЛИ всего подмассива равно нулю.
Таким образом, вы можете вычислить суммы префиксов XOR, поместить их в словарь и «на лету» проверить, существует ли уже в словаре правильная парная сумма.
Посмотрите на похожую задачу (обычные суммы, без XOR), также содержит трюк размера>=3
and "on the fly" check if proper pair sum already already exists in the dictionary можешь объяснить это утверждение, я не могу этого понять
@technotigr [5 3 2 1 7] xor суммы префиксов [5 6 4 5 6] для второй 5 у нас уже есть сумма 5, поэтому подсписок [3 2 1] является кандидатом на специальный подсписок (мы также должны проверить границы 3^ 1 против внутреннего 4^6)
so [3 2 1] sublist is candidate for special sublist (we have to check also borders 3^1 vs inner 4^6) можешь объяснить это подробнее, пожалуйста
@technotigr Две равные суммы префиксов говорят нам, что подсписок между соответствующими элементами имеет нулевую сумму xor - это понятно?
И последний вопрос we have to check also borders 3^1 vs inner 4^6 зачем это проверять? у нас уже есть специальный подсписок [3,2,1]
@technotigr Ага, моя ошибка в комментариях, он не нужен, любая часть подсписка с нулевой суммой дает нулевую сумму с остальной частью подсписка.
Отличное понимание. Алгоритм работает за O(n)!
Извините за путаницу. Я имел в виду: «Побитовое исключающее ИЛИ первого и последнего элемента в подмассиве равно побитовому исключающему ИЛИ для всех остальных элементов в подмассиве».