На сайте hackerrank.com есть отличная задача, в которой по заданному массиву short[] A нужно найти максимальное количество подмассивов, xor элементов которых будет одинаковым. Сам этот xor тоже нужно найти.
Постановка задачи
Пусть n — длина массива A, а m — искомое количество подмассивов. Тогда, массив A можно представить в виде последовательности битов: 0 или 1. Если элемент массива равен 0, то соответствующий бит равен 0 (false). Если элемент равен 1, тогда соответствующий бит равен 1 (true). Тогда для каждого бита массива i существует два подмассива, в точности совпадающие с ним по индексу элементов: один подмассив, содержащий только нули, и один подмассив с единицами. Например, если массив имеет вид 011010, то существует 4 подмассива: 01, 10, 11 и 00, при этом 01 и 10 должны быть объединены в один подмассив. Итак, каждый бит массива может быть связан с одним из этих двух подмассивов: либо подмассив единиц, либо подмассив нулей. Теперь рассмотрим все возможные комбинации этих подмассивов и их количества. Например, для массива 0100101 существует две комбинации: {0100, 01