Compruebe si el AND bit a bit de cualquier subconjunto es potencia de dos

Posted on by Rudeus Greyrat

Dada una array arr[] de n enteros positivos. La tarea es verificar si existe algún subconjunto de la array cuyo AND bit a bit sea una potencia de dos (es decir, 1, 2, 4, 8, 16, …).

Nota: Puede haber dos o más subconjuntos de una array dada cuyo AND bit a bit se convierte en potencia de dos. Devuelve SÍ si existe al menos un subconjunto; de lo contrario, devuelve NO.

Ejemplos: 

Input : n = 3, arr[] = { 12, 13, 7 }
Output : Yes
Explanation : Subset {12, 13, 7} and { 12, 7 } have Bitwise AND value 4 and 4 resepectively, which 
are power of 2.

Input : n = 2, arr[] = { 10, 20 }
Output : No

Observe, para que un número sea la potencia de 2, debe tener solo 1 bit establecido. 
Si n es 1, simplemente verificamos si el número tiene el único bit establecido. 
Para n es mayor que uno, nuestra tarea es elegir aquellos números de la array cuyo AND bit a bit conduce a un conjunto de números de un solo bit. Para ello, buscamos una posición en la que todos los elementos del conjunto tengan un bit establecido en esa posición. Por ejemplo, para establecer { 4 (100), 6 (110), 7 (111) }, en la posición 2 (de derecha a izquierda, indexación basada en 0) el bit se establece para todos los elementos. Entonces, hacer AND bit a bit da 4, que es una potencia de 2.
A continuación se muestra la implementación de este enfoque: 

Ilustración : 

12 –> 01100

13 –> 01101

7 –> 00111

Para la posición = 0 (de derecha a izquierda, indexación basada en 0), existen 13 y 17 cuyo bit es setbit.

totales –> 11111111111111111111111

13 –> 0000000000000000001101

7 –> 0000000000000000000111

                             —————————–

bit a bit Y –> 0000000000000000000101

AND bit a bit no es potencia de 2, por lo que no es un subconjunto válido.

Para la posición = 1, existen solo 7 cuyo bit es setbit.

totales –> 11111111111111111111111

7 –> 0000000000000000000111

                            ——————————

bit a bit Y –> 0000000000000000000111

AND bit a bit no es potencia de 2, por lo que no es un subconjunto válido.

Para posición = 2, existen 12, 13 y 7 cuyo bit es setbit.

totales –> 11111111111111111111111

12 –> 0000000000000000001100

13 –> 0000000000000000001101

7 –> 0000000000000000000111

                            ——————————

bit a bit Y –> 0000000000000000000100

AND bit a bit es potencia de 2 por lo que es un subconjunto válido.

Del mismo modo, podemos comprobar las posiciones restantes.

Algoritmo: 

  1. Si el tamaño de la array es 1, simplemente verifique si el primer elemento de la array es potencia de 2 o no.
  2. De lo contrario, cree una variable total = 0 y convierta todos sus bits en setbit.
  3. Recorra desde i=0 hasta i = 31 para cada bit.
  4. Crea una variable ans = total.
  5. Atraviese una array y si el bit del elemento actual en la posición i se establece como bit, cambie la variable ans a AND bit a bit del elemento ans y actual.
  6. Después de completar el recorrido en la array. Comprueba nuestra respuesta si es potencia de dos o no.
  7. Si ans es potencia de dos, devuelve verdadero. De lo contrario, atraviese para el siguiente bit.
  8. Después de recorrer cada bit, si no encontramos ningún subconjunto, devuelve falso.

Implementación:

C++

// CPP Program to check if Bitwise AND of any
// subset is power of two
#include <bits/stdc++.h>
using namespace std;
 
const int NUM_BITS = 32;
 
// Check for power of 2 or not
bool isPowerOf2(int num)
{
    return (num && !(num & (num - 1)));
}
 
// Check if there exist a subset whose bitwise AND
// is power of 2.
bool checkSubsequence(int arr[], int n)
{
    // if there is only one element in the set.
    if (n == 1)
       return isPowerOf2(arr[0]);
 
    // Finding a number with all bit sets.
    int total = 0;
    for (int i = 0; i < NUM_BITS; i++)
        total = total | (1 << i);
 
    // check all the positions at which the bit is set.
    for (int i = 0; i < NUM_BITS; i++) {
 
        int ans = total;
        for (int j = 0; j < n; j++) {
 
            // include all those elements whose
            // i-th bit is set
            if (arr[j] & (1 << i))
                ans = ans & arr[j];
        }
 
        // check for the set contains elements
        // make a power of 2 or not
        if (isPowerOf2(ans))
            return true;
    }
    return false;
}
 
// Driver Program
int main()
{
    int arr[] = { 12, 13, 7 };
    int n = sizeof(arr) / sizeof(arr[0]);
    if (checkSubsequence(arr, n))
        printf("YES\n");
    else
        printf("NO\n");
    return 0;
}

Java

// Java Program to check if Bitwise AND of any
// subset is power of two
import java.io.*;
import java.util.*;
 
public class GFG {
      
    static int NUM_BITS = 32;
      
    // Check for power of 2 or not
    static boolean isPowerOf2(int num)
    {
        if(num != 0 && (num & (num - 1)) == 0)
            return true;
        return false;
    }
      
    // Check if there exist a
    // subset whose bitwise AND
    // is power of 2.
    static boolean checkSubsequence(int []arr, int n)
    {
          
        // if there is only one
        // element in the set.
        if (n == 1)
            return isPowerOf2(arr[0]);
      
        // Finding a number with
        // all bit sets.
        int total = 0;
        for (int i = 0; i < NUM_BITS; i++)
            total = total | (1 << i);
      
        // check all the positions
        // at which the bit is set.
        for (int i = 0; i < NUM_BITS; i++)
        {
      
            int ans = total;
            for (int j = 0; j < n; j++)
            {
      
                // include all those
                // elements whose
                // i-th bit is set
                int p = arr[j] & (1 << i);
                if (p == 0)
                    ans = ans & arr[j];
            }
      
            // check for the set
            // contains elements
            // make a power of 2
            // or not
            if (isPowerOf2(ans))
                return true;
        }
        return false;
    }
      
    // Driver Code
    public static void main(String args[])
    {
        int []arr = {12, 13, 7};
        int n = arr.length;
        if (checkSubsequence(arr, n))
            System.out.println("YES");
        else
            System.out.println("NO");
    }
}
  
// This code is contributed by
// Manish Shaw (manishshaw1)

Python3

# Python3 Program to check if Bitwise AND of any
# subset is power of two
  
NUM_BITS = 32
  
# Check for power of 2 or not
def isPowerOf2(num):
    return (num and (num & (num - 1)) == 0)
  
# Check if there exist a subset whose bitwise AND
# is power of 2.
def checkSubsequence(arr, n):
 
    # if there is only one element in the set.
    if (n == 1):
        return isPowerOf2(arr[0])
  
    # Finding a number with all bit sets.
    total = 0
    for i in range(0, NUM_BITS):
        total = total | (1 << i)
  
    # check all the positions at which the bit is set.
    for i in range(0, NUM_BITS):
  
        ans = total
        for j in range(0, n):
 
            # include all those elements whose
            # i-th bit is set
            if (arr[j] & (1 << i)):
                ans = ans & arr[j]
  
        # check for the set contains elements
        # make a power of 2 or not
        if (isPowerOf2(ans)):
            return True
    return False
  
# Driver Program
arr = [ 12, 13, 7 ]
n = len(arr)
if (checkSubsequence(arr, n)):
    print ("YES\n")
else:
    print ("NO\n")
 
# This code is contributed by Manish Shaw
# (manishshaw1)

C#

// C# Program to check if Bitwise AND of any
// subset is power of two
using System;
using System.Collections.Generic;
 
class GFG {
     
    static int NUM_BITS = 32;
     
    // Check for power of 2 or not
    static bool isPowerOf2(int num)
    {
        if(num != 0 && (num & (num - 1)) == 0)
            return true;
        return false;
    }
     
    // Check if there exist a
    // subset whose bitwise AND
    // is power of 2.
    static bool checkSubsequence(int []arr, int n)
    {
         
        // if there is only one
        // element in the set.
        if (n == 1)
            return isPowerOf2(arr[0]);
     
        // Finding a number with
        // all bit sets.
        int total = 0;
        for (int i = 0; i < NUM_BITS; i++)
            total = total | (1 << i);
     
        // check all the positions
        // at which the bit is set.
        for (int i = 0; i < NUM_BITS; i++)
        {
     
            int ans = total;
            for (int j = 0; j < n; j++)
            {
     
                // include all those
                // elements whose
                // i-th bit is set
                int p = arr[j] & (1 << i);
                if (p == 0)
                    ans = ans & arr[j];
            }
     
            // check for the set
            // contains elements
            // make a power of 2
            // or not
            if (isPowerOf2(ans))
                return true;
        }
        return false;
    }
     
    // Driver Code
    public static void Main()
    {
        int []arr = {12, 13, 7};
        int n = arr.Length;
        if (checkSubsequence(arr, n))
            Console.Write("YES\n");
        else
            Console.Write("NO\n");
    }
}
 
// This code is contributed by
// Manish Shaw (manishshaw1)

PHP

<?php
// PHP Program to check if
// Bitwise AND of any subset
// is power of two
 
// Check for power of 2 or not
function isPowerOf2($num)
{
    return ($num && !($num & ($num - 1)));
}
 
// Check if there exist a
// subset whose bitwise AND
// is power of 2.
function checkSubsequence($arr, $n)
{
    $NUM_BITS = 32;
     
    // if there is only one
    // element in the set.
    if ($n == 1)
    return isPowerOf2($arr[0]);
 
    // Finding a number with
    // all bit sets.
    $total = 0;
    for($i = 0; $i < $NUM_BITS; $i++)
        $total = $total | (1 << $i);
 
    // check all the positions at
    // which the bit is set.
    for($i = 0; $i < $NUM_BITS; $i++)
    {
 
        $ans = $total;
        for ($j = 0; $j < $n; $j++)
        {
 
            // include all those
            // elements whose
            // i-th bit is set
            if ($arr[$j] & (1 << $i))
                $ans = $ans & $arr[$j];
        }
 
        // check for the set
        // contains elements
        // make a power of 2 or not
        if (isPowerOf2($ans))
            return true;
    }
    return false;
}
 
    // Driver Code
    $arr= array(12, 13, 7);
    $n = sizeof($arr) / sizeof($arr[0]);
    if (checkSubsequence($arr, $n))
        echo "YES";
    else
        echo "NO";
 
// This code is contributed by mits
?>

Javascript

<script>
 
// Javascript Program to check if Bitwise AND of any
// subset is power of two
 
var NUM_BITS = 32;
 
// Check for power of 2 or not
function isPowerOf2(num)
{
    return (num && !(num & (num - 1)));
}
 
// Check if there exist a subset whose bitwise AND
// is power of 2.
function checkSubsequence(arr, n)
{
 
    // if there is only one element in the set.
    if (n == 1)
       return isPowerOf2(arr[0]);
 
    // Finding a number with all bit sets.
    var total = 0;
    for (var i = 0; i < NUM_BITS; i++)
        total = total | (1 << i);
 
    // check all the positions at which the bit is set.
    for (var i = 0; i < NUM_BITS; i++) {
 
        var ans = total;
        for (var j = 0; j < n; j++) {
 
            // include all those elements whose
            // i-th bit is set
            if (arr[j] & (1 << i))
                ans = ans & arr[j];
        }
 
        // check for the set contains elements
        // make a power of 2 or not
        if (isPowerOf2(ans))
            return true;
    }
    return false;
}
 
// Driver Program
var arr = [ 12, 13, 7 ];
var n = arr.length;
if (checkSubsequence(arr, n))
    document.write("YES<br>");
else
    document.write("NO<br>");
 
// This code is contributed by itsok.
</script>
Producción: 

YES

 

Complejidad de tiempo : O(N)

  • [(32)* (longitud de la array) donde 32 es el tiempo constante, por lo que, según el árbol de recurrencia, la complejidad del tiempo es de orden N]

Espacio Auxiliar : O(1)

Referencia:  
https://stackoverflow.com/questions/35990794/subset-of-array-a-in-which-if-we-do-and-of-all-elements-of-that-subset-then-outp
 

Publicación traducida automáticamente

Artículo escrito por anuj0503 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 *