Рубрики

Способы разделения массива на две группы с одинаковым значением XOR

Дан массив A из n целых чисел. Задача состоит в том, чтобы подсчитать количество способов разбить данные элементы массива на две непересекающиеся группы так, чтобы XOR элементов каждой группы был равен.

Примеры:

Input : A[] = { 1, 2, 3 }
Output : 3
{(1), (2, 3)}, {(2), (1, 3)}, {(3), (1, 2)} 
are three ways with equal XOR value of two
groups.

Input :  A[] = { 5, 2, 3, 2 }
Output : 0

Обозначим XOR между всеми элементами в первой группе как G 1, а XOR между всеми элементами во второй группе как G 2 . Теперь следующее соотношение всегда корректно: G 1 ⊕ G 2 = A 1 ⊕ A 2 ⊕…. N A n .
Таким образом, для G 1 = G 2 xor между всеми элементами массива A равно 0. Таким образом, в этом случае ответ будет (2 n — 2) / 2 = (2 n-1 — 1). Во втором случае, когда XOR между всеми элементами не равен 0, мы не можем разделить массив. Ответ будет 0.

C ++

// Программа CPP для подсчета количества способов разделения
// массив на две группы, так что каждая группа
// имеет равное значение XOR
#include<bits/stdc++.h>

using namespace std;

  
// Возвращаем количество способов разделения
// массив на две группы, так что каждая группа
// имеет равное значение XOR.

int countgroup(int a[], int n)

{

  int xs = 0;

  for (int i = 0; i < n; i++)

    xs = xs ^ a[i];

  

  // Мы можем разделить только если XOR равен 0. Так как

  // XOR всего равно 0, мы можем рассмотреть все

  // подмножества как одна группа.

  if (xs == 0)

    return (1 << (n-1)) - 1;

  

  return 0;

}

  
// Программа для водителя

int main()

{

  int a[] = { 1, 2, 3 };

  int n = sizeof(a)/sizeof(a[0]);

  cout << countgroup(a, n) << endl;

  return 0;

Джава

// Java-программа для подсчета количества способов
// разбить массив на две группы такие
// каждая группа имеет одинаковое значение XOR

import java.io.*;

import java.util.*;

  

class GFG {

  
// Возвращаем количество способов разделения
// массив на две группы, так что каждая группа
// имеет равное значение XOR.

static int countgroup(int a[], int n) {

    int xs = 0;

    for (int i = 0; i < n; i++)

    xs = xs ^ a[i];

  

    // Мы можем разделить только если XOR равен 0. Так как

    // XOR всего равно 0, мы можем рассмотреть все

    // подмножества как одна группа.

    if (xs == 0)

    return (1 << (n - 1)) - 1;

  

    return 0;

}

  
// Драйвер программы

public static void main(String args[]) {

    int a[] = {1, 2, 3};

    int n = a.length;

    System.out.println(countgroup(a, n));

}
}

  
// Этот код предоставлен Никитой Тивари.

python3

# Python3 код для подсчета количества способов
# разбить массив на две группы такие
# что каждая группа имеет равное значение XOR

  
# Вернуть счетчик количества способов
# разбить массив на две группы такие
# что каждая группа имеет одинаковое значение XOR.

def countgroup(a, n):

    xs = 0

    for i in range(n):

        xs = xs ^ a[i]

      

    # Мы можем разделить, только если XOR равен 0.

    # Поскольку XOR для всех равно 0, мы можем

    # рассматривать все подмножества как одну группу.

    if xs == 0:

        return (1 << (n-1)) - 1

      

    return 0

      
# Драйверная программа

a = [1, 2, 3]

n = len(a)

print(countgroup(a, n)) 

  
# Этот код предоставлен "Sharad_Bhardwaj".

C #

// C # Программа для подсчета количества способов
// разбить массив на две группы такие
// каждая группа имеет одинаковое значение XOR

using System;

  

class GFG {

  

    // Возвращаем количество способов разделения

    // массив на две группы, так что каждая группа

    // имеет равное значение XOR.

    static int countgroup(int[] a, int n)

    {

        int xs = 0;

        for (int i = 0; i < n; i++)

            xs = xs ^ a[i];

  

        // Мы можем разделить только если XOR равен 0. Так как

        // XOR всего равно 0, мы можем рассмотреть все

        // подмножества как одна группа.

        if (xs == 0)

            return (1 << (n - 1)) - 1;

  

        return 0;

    }

  

    // Драйвер программы

    public static void Main()

    {

        int[] a = { 1, 2, 3 };

        int n = a.Length;

        Console.WriteLine(countgroup(a, n));

    }

}

  
// Этот код предоставлен vt_m.

PHP

<?php
// PHP программа для подсчета числа
// способов разбить массив на
// две группы такие, что каждая
// группа имеет равное значение XOR

  
// Возвращаем количество
// способы разбить массив на
// две группы такие, что каждая
// grouphas равно значению XOR.

function countgroup($a, $n)

{

    $xs = 0;

    for ($i = 0; $i < $n; $i++)

        $xs = $xs ^ $a[$i];

      

    // Мы можем разделить только если XOR равен 0. Так как

    // XOR всего равно 0, мы можем рассмотреть все

    // подмножества как одна группа.

    if ($xs == 0)

        return (1 << ($n - 1)) - 1;

      

    return 0;

}

  
// Код драйвера

$a = array(1, 2, 3);

$n = count($a);

echo countgroup($a, $n);

  
// Этот код предоставлен anuj_67.
?>


Выход:

3

Рекомендуемые посты:

Способы разделения массива на две группы с одинаковым значением XOR

0.00 (0%) 0 votes