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

30.12.2019Массивы, Немного магии

Дан массив 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 ₂ . Теперь следующее соотношение всегда корректно: G ₁ ⊕ G ₂ = A ₁ ⊕ A ₂ ⊕…. _N A _n .
Таким образом, для G ₁ = G ₂ xor между всеми элементами массива A равно 0. Таким образом, в этом случае ответ будет (2 ⁿ — 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 {

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.
?>

Выход:

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

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

0.00 (0%) 0 votes