найти общее количество способов XOR для массива целых чисел, чтобы получить ноль

Question

Если у нас есть массив целых чисел, то как мы можем найти количество способов их XORed, чтобы результат был 0.Здесь на каждом шаге можно уменьшить только одно целое число (i) на любую величину, скажем, d, так что (id)> = 0.Например, для целых чисел 11,15,8 мы можем decrease 11 to 7, чтобы 7 ^ 15 ^ 8 = 0.Сходные 15 can be reduced to 3 такие, что 11 ^ 3 ^ 8 = 0 и 8 can be reduced to 4 такие, что 11 ^ 15 ^ 4 = 0.Следовательно, общее число путей равно 3

Мой подход : это для каждого целого числа, продолжайте уменьшать его и на каждом шаге XOR с остальными целыми числами в массиве, если результат равен 0,перерыв.Проверьте это для всех целых чисел и получите общее количество способов.Но это 0 (п ^ 2).Есть ли эффективный способ сделать это?Спасибо.

Answer 1

Вы можете XOR все целые числа в вашем массиве, а затем в цикле XOR результат с каждым из ваших целых чисел (это "удалит" это целое число из всех, потому что x^x всегда равно 0). В результате вы получите XOR других участников, и это число будет заменено (потому что x^x всегда 0).

    int[] a = new int [size];
    //initialize 'a' array
    int[] b = new int [size];
    int all = 0;
    for(int i = 0; i<a.length; i++)
        all=all^a[i];

    for(int i =0; i< size; i++)
        b[i] = all^a[i];

В b[i] вы получите номер, который нужно заменить на a[i], чтобы получить ноль.
Я отредактировал свой ответ и попытался, это работает. Это O (n).

Answer 2

Это очень похоже на поиск k чисел в массиве длины, сумма которых равна x.

Для k = 1: очевидно. Найти элементы, которые равны 0

Для k = 2: сортировать числа и для каждого номера проверять наличие 0 ^ a в массиве

Для k = 3: отсортировать числа и для каждой пары чисел a и b проверить, существует ли в массиве a ^ b ^ 0

Для k = 4: вычислить xors каждых двух чисел в массиве и отсортировать. И для каждой пары чисел a и b проверьте, существует ли a ^ b ^ 0 в отсортированном списке

и т. Д.

Для k = 1 сложность O (n), k-2: nlogn, k = 3: n ^ 2logn, k = 4: n ^ 2logn и т. Д.