Número de subconjuntos con los mismos valores AND, OR y XOR en una array

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:
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:

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: 
    1. El tamaño del subconjunto es impar : el valor XOR es igual a x.
    2. 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 )

Publicación traducida automáticamente

Artículo escrito por king_tsar y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA

Deja una respuesta

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *