Dada una array arr[] de tamaño N que consta de enteros no negativos, la tarea es encontrar el número de subconjuntos no vacíos de la array de modo que los valores AND bit a bit, OR bit a bit y XOR bit a bit de la subsecuencia sean iguales a cada uno . otro.
Nota: dado que la respuesta puede ser grande, modifíquela con 1000000007 .
Ejemplos:
Entrada: arr[] = [1, 3, 2, 1, 2, 1]
Salida: 7
Explicación:
Una de las subsecuencias con igual bit a bit Xor, bit a bit or y bit a bit AND es {1, 1, 1}.Entrada: arr = [2, 3, 4, 5]
Salida: 4
Enfoque ingenuo El enfoque ingenuo para este problema es atravesar todos los subconjuntos de la array de manera iterativa, y para cada subconjunto encontrar el valor AND, OR y XOR bit a bit y verificar si son iguales o no. Finalmente, devuelva el recuento de tales subconjuntos iguales.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ implementation to find the number
// of subsets with equal bitwise AND,
// OR and XOR values
#include <bits/stdc++.h>
using namespace std;
const int mod = 1000000007;
// Function to find the number of
// subsets with equal bitwise AND,
// OR and XOR values
int countSubsets(int a[], int n)
{
int answer = 0;
// Traverse through all the subsets
for (int i = 0; i < (1 << n); i++) {
int bitwiseAND = -1;
int bitwiseOR = 0;
int bitwiseXOR = 0;
// Finding the subsets with the bits
// of 'i' which are set
for (int j = 0; j < n; j++) {
// Computing the bitwise AND
if (i & (1 << j)) {
if (bitwiseAND == -1)
bitwiseAND = a[j];
else
bitwiseAND &= a[j];
// Computing the bitwise OR
bitwiseOR |= a[j];
// Computing the bitwise XOR
bitwiseXOR ^= a[j];
}
}
// Comparing all the three values
if (bitwiseAND == bitwiseOR
&& bitwiseOR == bitwiseXOR)
answer = (answer + 1) % mod;
}
return answer;
}
// Driver code
int main()
{
int N = 6;
int A[N] = { 1, 3, 2, 1, 2, 1 };
cout << countSubsets(A, N);
return 0;
}
Java
// Java implementation to find the number
// of subsets with equal bitwise AND,
// OR and XOR values
import java.io.*;
class GFG {
static int mod = 1000000007;
// Function to find the number of
// subsets with equal bitwise AND,
// OR and XOR values
static int countSubsets(int a[], int n)
{
int answer = 0;
// Traverse through all the subsets
for (int i = 0; i < (1 << n); i++) {
int bitwiseAND = -1;
int bitwiseOR = 0;
int bitwiseXOR = 0;
// Finding the subsets with the bits
// of 'i' which are set
for (int j = 0; j < n; j++) {
// Computing the bitwise AND
if ((i & (1 << j)) == 0) {
if (bitwiseAND == -1)
bitwiseAND = a[j];
else
bitwiseAND &= a[j];
// Computing the bitwise OR
bitwiseOR |= a[j];
// Computing the bitwise XOR
bitwiseXOR ^= a[j];
}
}
// Comparing all the three values
if (bitwiseAND == bitwiseOR
&& bitwiseOR == bitwiseXOR)
answer = (answer + 1) % mod;
}
return answer;
}
// Driver Code
public static void main (String[] args)
{
int N = 6;
int A[] = { 1, 3, 2, 1, 2, 1 };
System.out.print(countSubsets(A, N));
}
}
// This code is contributed by shivanisinghss2110
Python3
# Python3 implementation to find the number # of subsets with equal bitwise AND, # OR and XOR values mod = 1000000007; # Function to find the number of # subsets with equal bitwise AND, # OR and XOR values def countSubsets(a, n) : answer = 0; # Traverse through all the subsets for i in range(1 << n) : bitwiseAND = -1; bitwiseOR = 0; bitwiseXOR = 0; # Finding the subsets with the bits # of 'i' which are set for j in range(n) : # Computing the bitwise AND if (i & (1 << j)) : if (bitwiseAND == -1) : bitwiseAND = a[j]; else : bitwiseAND &= a[j]; # Computing the bitwise OR bitwiseOR |= a[j]; # Computing the bitwise XOR bitwiseXOR ^= a[j]; # Comparing all the three values if (bitwiseAND == bitwiseOR and bitwiseOR == bitwiseXOR) : answer = (answer + 1) % mod; return answer; # Driver code if __name__ == "__main__" : N = 6; A = [ 1, 3, 2, 1, 2, 1 ]; print(countSubsets(A, N)); # This code is contributed by AnkitRai01
C#
// C# implementation to find the number
// of subsets with equal bitwise AND,
// OR and XOR values
using System;
class GFG {
static int mod = 1000000007;
// Function to find the number of
// subsets with equal bitwise AND,
// OR and XOR values
static int countSubsets(int []a, int n)
{
int answer = 0;
// Traverse through all the subsets
for (int i = 0; i < (1 << n); i++) {
int bitwiseAND = -1;
int bitwiseOR = 0;
int bitwiseXOR = 0;
// Finding the subsets with the bits
// of 'i' which are set
for (int j = 0; j < n; j++) {
// Computing the bitwise AND
if ((i & (1 << j)) == 0) {
if (bitwiseAND == -1)
bitwiseAND = a[j];
else
bitwiseAND &= a[j];
// Computing the bitwise OR
bitwiseOR |= a[j];
// Computing the bitwise XOR
bitwiseXOR ^= a[j];
}
}
// Comparing all the three values
if (bitwiseAND == bitwiseOR
&& bitwiseOR == bitwiseXOR)
answer = (answer + 1) % mod;
}
return answer;
}
// Driver Code
public static void Main(String[] args)
{
int N = 6;
int []A = { 1, 3, 2, 1, 2, 1 };
Console.Write(countSubsets(A, N));
}
}
// This code is contributed by 29AjayKumar
Javascript
<script>
// Javascript implementation to find the number
// of subsets with equal bitwise AND,
// OR and XOR values
let mod = 1000000007;
// Function to find the number of
// subsets with equal bitwise AND,
// OR and XOR values
function countSubsets(a, n)
{
let answer = 0;
// Traverse through all the subsets
for (let i = 0; i < (1 << n); i++) {
let bitwiseAND = -1;
let bitwiseOR = 0;
let bitwiseXOR = 0;
// Finding the subsets with the bits
// of 'i' which are set
for (let j = 0; j < n; j++) {
// Computing the bitwise AND
if ((i & (1 << j)) != 0) {
if (bitwiseAND == -1)
bitwiseAND = a[j];
else
bitwiseAND &= a[j];
// Computing the bitwise OR
bitwiseOR |= a[j];
// Computing the bitwise XOR
bitwiseXOR ^= a[j];
}
}
// Comparing all the three values
if (bitwiseAND == bitwiseOR
&& bitwiseOR == bitwiseXOR)
answer = (answer + 1) % mod;
}
return answer;
}
let N = 6;
let A = [ 1, 3, 2, 1, 2, 1 ];
document.write(countSubsets(A, N));
</script>
Producción:
7
Complejidad de tiempo: O(N * 2 N ) donde N es el tamaño de la array.
Espacio Auxiliar: O(1)
Enfoque eficiente: el enfoque eficiente se encuentra detrás de la propiedad de las operaciones bit a bit.
- Usando la propiedad de AND bit a bit, y OR bit a bit podemos decir que si a & b == a | b, entonces a es igual a b. Entonces, si los valores AND y OR del subconjunto son iguales, entonces todos los elementos del subconjunto son idénticos (por ejemplo, x). Entonces los valores AND y OR son iguales a x.
- Dado que todos los valores de la subsecuencia son iguales entre sí, surgen dos casos para el valor XOR:
- El tamaño del subconjunto es impar : el valor XOR es igual a x.
- El tamaño del subconjunto es par : los valores XOR son iguales a 0.
- Por lo tanto, a partir de la observación anterior, podemos llegar a la conclusión de que todas las subsecuencias/subconjuntos de tamaño impar con elementos iguales siguen la propiedad.
- Además de esto, si todos los elementos del subconjunto son 0, entonces el subconjunto seguirá la propiedad (independientemente del tamaño del subconjunto). Entonces, todos los subconjuntos que tienen solo 0 como elemento se agregarán a la respuesta.
- Si la frecuencia de algún elemento es K, entonces el número de subconjuntos de tamaño impar que puede formar es 2 K – 1 , y el total de subconjuntos no vacíos que puede formar es 2 K – 1 .
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program to find the number
// of subsets with equal bitwise
// AND, OR and XOR values
#include <bits/stdc++.h>
using namespace std;
const int mod = 1000000007;
// Function to find the number of
// subsets with equal bitwise AND,
// OR and XOR values
int countSubsets(int a[], int n)
{
int answer = 0;
// Precompute the modded powers
// of two for subset counting
int powerOfTwo[100005];
powerOfTwo[0] = 1;
// Loop to iterate and find the modded
// powers of two for subset counting
for (int i = 1; i < 100005; i++)
powerOfTwo[i]
= (powerOfTwo[i - 1] * 2)
% mod;
// Map to store the frequency of
// each element
unordered_map<int, int> frequency;
// Loop to compute the frequency
for (int i = 0; i < n; i++)
frequency[a[i]]++;
// For every element > 0, the number of
// subsets formed using this element only
// is equal to 2 ^ (frequency[element]-1).
// And for 0, we have to find all
// the subsets, so 2^(frequency[element]) -1
for (auto el : frequency) {
// If element is greater than 0
if (el.first != 0)
answer
= (answer % mod
+ powerOfTwo[el.second - 1])
% mod;
else
answer
= (answer % mod
+ powerOfTwo[el.second]
- 1 + mod)
% mod;
}
return answer;
}
// Driver code
int main()
{
int N = 6;
int A[N] = { 1, 3, 2, 1, 2, 1 };
cout << countSubsets(A, N);
return 0;
}
Java
// Java program to find the number
// of subsets with equal bitwise
// AND, OR and XOR values
import java.util.*;
class GFG{
static int mod = 1000000007;
// Function to find the number of
// subsets with equal bitwise AND,
// OR and XOR values
static int countSubsets(int a[], int n)
{
int answer = 0;
// Precompute the modded powers
// of two for subset counting
int []powerOfTwo = new int[100005];
powerOfTwo[0] = 1;
// Loop to iterate and find the modded
// powers of two for subset counting
for (int i = 1; i < 100005; i++)
powerOfTwo[i]
= (powerOfTwo[i - 1] * 2)
% mod;
// Map to store the frequency of
// each element
HashMap<Integer,Integer> frequency = new HashMap<Integer,Integer>();
// Loop to compute the frequency
for (int i = 0; i < n; i++)
if(frequency.containsKey(a[i])){
frequency.put(a[i], frequency.get(a[i])+1);
}else{
frequency.put(a[i], 1);
}
// For every element > 0, the number of
// subsets formed using this element only
// is equal to 2 ^ (frequency[element]-1).
// And for 0, we have to find all
// the subsets, so 2^(frequency[element]) -1
for (Map.Entry<Integer,Integer> el : frequency.entrySet()) {
// If element is greater than 0
if (el.getKey() != 0)
answer
= (answer % mod
+ powerOfTwo[el.getValue() - 1])
% mod;
else
answer
= (answer % mod
+ powerOfTwo[el.getValue()]
- 1 + mod)
% mod;
}
return answer;
}
// Driver code
public static void main(String[] args)
{
int N = 6;
int A[] = { 1, 3, 2, 1, 2, 1 };
System.out.print(countSubsets(A, N));
}
}
// This code is contributed by 29AjayKumar
Python3
# Python3 program to find the number
# of subsets with equal bitwise
# AND, OR and XOR values
mod = 1000000007
# Function to find the number of
# subsets with equal bitwise AND,
# OR and XOR values
def countSubsets(a, n):
answer = 0
# Precompute the modded powers
# of two for subset counting
powerOfTwo = [0 for x in range(100005)]
powerOfTwo[0] = 1
# Loop to iterate and find the modded
# powers of two for subset counting
for i in range(1, 100005):
powerOfTwo[i] = (powerOfTwo[i - 1] * 2) % mod
# Map to store the frequency of
# each element
frequency = {}
# Loop to compute the frequency
for i in range(0, n):
if a[i] in frequency:
frequency[a[i]] += 1
else:
frequency[a[i]] = 1
# For every element > 0, the number of
# subsets formed using this element only
# is equal to 2 ^ (frequency[element]-1).
# And for 0, we have to find all
# the subsets, so 2^(frequency[element]) -1
for key, value in frequency.items():
# If element is greater than 0
if (key != 0):
answer = (answer % mod +
powerOfTwo[value - 1]) % mod
else:
answer = (answer % mod +
powerOfTwo[value] - 1 + mod)% mod
return answer
# Driver code
N = 6
A = [ 1, 3, 2, 1, 2, 1 ]
print(countSubsets(A, N))
# This code is contributed by amreshkumar3
C#
// C# program to find the number
// of subsets with equal bitwise
// AND, OR and XOR values
using System;
using System.Collections.Generic;
class GFG{
static int mod = 1000000007;
// Function to find the number of
// subsets with equal bitwise AND,
// OR and XOR values
static int countSubsets(int []a, int n)
{
int answer = 0;
// Precompute the modded powers
// of two for subset counting
int []powerOfTwo = new int[100005];
powerOfTwo[0] = 1;
// Loop to iterate and find the modded
// powers of two for subset counting
for(int i = 1; i < 100005; i++)
powerOfTwo[i] = (powerOfTwo[i - 1] * 2) % mod;
// Map to store the frequency
// of each element
Dictionary<int, int> frequency = new Dictionary<int, int>();
// Loop to compute the frequency
for(int i = 0; i < n; i++)
if(frequency.ContainsKey(a[i]))
{
frequency[a[i]] = frequency[a[i]] + 1;
}
else
{
frequency.Add(a[i], 1);
}
// For every element > 0, the number of
// subsets formed using this element only
// is equal to 2 ^ (frequency[element]-1).
// And for 0, we have to find all
// the subsets, so 2^(frequency[element]) -1
foreach (KeyValuePair<int, int> el in frequency)
{
// If element is greater than 0
if (el.Key != 0)
answer = (answer % mod +
powerOfTwo[el.Value - 1]) % mod;
else
answer = (answer % mod +
powerOfTwo[el.Value] - 1 +
mod) % mod;
}
return answer;
}
// Driver code
public static void Main(String[] args)
{
int N = 6;
int []A = { 1, 3, 2, 1, 2, 1 };
Console.Write(countSubsets(A, N));
}
}
// This code is contributed by Rajput-Ji
Javascript
<script>
// Javascript program to find the number
// of subsets with equal bitwise
// AND, OR and XOR values
var mod = 1000000007;
// Function to find the number of
// subsets with equal bitwise AND,
// OR and XOR values
function countSubsets(a, n)
{
var answer = 0;
// Precompute the modded powers
// of two for subset counting
var powerOfTwo = Array(100005).fill(0);
powerOfTwo[0] = 1;
// Loop to iterate and find the modded
// powers of two for subset counting
for(var i = 1; i < 100005; i++)
powerOfTwo[i] = (powerOfTwo[i - 1] * 2) % mod;
// Map to store the frequency
// of each element
var frequency = new Map();
// Loop to compute the frequency
for(var i = 0; i < n; i++)
if (frequency.has(a[i]))
{
frequency.set(a[i], frequency.get(a[i]) + 1);
}
else
{
frequency.set(a[i], 1);
}
// For every element > 0, the number of
// subsets formed using this element only
// is equal to 2 ^ (frequency[element]-1).
// And for 0, we have to find all
// the subsets, so 2^(frequency[element]) -1
frequency.forEach((value, key) => {
// If element is greater than 0
if (key != 0)
answer = (answer % mod +
powerOfTwo[value - 1]) % mod;
else
answer = (answer % mod +
powerOfTwo[value] - 1 +
mod) % mod;
});
return answer;
}
// Driver code
var N = 6;
var A = [ 1, 3, 2, 1, 2, 1 ];
document.write(countSubsets(A, N));
// This code is contributed by rrrtnx
</script>
Producción:
7
Complejidad de tiempo: O(N) , donde N es el tamaño de la array.
Espacio Auxiliar: O(N + 10 5 )