Bitwise OR de Bitwise AND de todos los subarreglos de un arreglo

Posted on by Rudeus Greyrat

Dada una array arr[] que consta de N enteros positivos, la tarea es encontrar el OR bit a bit de AND bit a bit de todos los subarreglos de las arrays dadas.

Ejemplos:

Entrada: arr[] = {1, 2, 3}
Salida: 3
Explicación:
Los siguientes son bits Y de todos los subarreglos posibles son:

  1. {1}, AND bit a bit es 1.
  2. {1, 2}, AND bit a bit es 0.
  3. {1, 2, 3}, AND bit a bit es 0.
  4. {2}, AND bit a bit es 2.
  5. {2, 3}, AND bit a bit es 2.
  6. {3}, AND bit a bit es 3.

El OR bit a bit de todos los valores anteriores es 3.

Entrada: arr[] = {1, 4, 2, 10}
Salida: 15

Enfoque ingenuo: el enfoque más simple para resolver el problema dado es generar todos los subarreglos posibles de la array dada y luego encontrar el OR bit a bit de todos los AND bit a bit de todos los subarreglos generados como resultado.

A continuación se muestra la implementación del enfoque anterior:

C++

// C++ program for the above approach
 
#include <bits/stdc++.h>
using namespace std;
 
// Function to find the Bitwise OR
// of Bitwise AND of all subarrays
void findbitwiseOR(int* a, int n)
{
    // Stores the required result
    int res = 0;
 
    // Generate all the subarrays
    for (int i = 0; i < n; i++) {
 
        // Store the current element
        int curr_sub_array = a[i];
 
        // Find the Bitwise OR
        res = res | curr_sub_array;
 
        for (int j = i; j < n; j++) {
 
            // Update the result
            curr_sub_array = curr_sub_array
                             & a[j];
            res = res | curr_sub_array;
        }
    }
 
    // Print the result
    cout << res;
}
 
// Driver Code
int main()
{
    int A[] = { 1, 2, 3 };
    int N = sizeof(A) / sizeof(A[0]);
    findbitwiseOR(A, N);
 
    return 0;
}

Java

// Java program for the above approach
public class GFG {
 
    // Function to find the Bitwise OR
    // of Bitwise AND of all subarrays
    static void findbitwiseOR(int[] a, int n)
    {
        // Stores the required result
        int res = 0;
 
        // Generate all the subarrays
        for (int i = 0; i < n; i++) {
 
            // Store the current element
            int curr_sub_array = a[i];
 
            // Find the Bitwise OR
            res = res | curr_sub_array;
 
            for (int j = i; j < n; j++) {
 
                // Update the result
                curr_sub_array = curr_sub_array & a[j];
                res = res | curr_sub_array;
            }
        }
 
        // Print the result
        System.out.println(res);
    }
    // Driver code
    public static void main(String[] args)
    {
        int A[] = { 1, 2, 3 };
        int N = A.length;
        findbitwiseOR(A, N);
    }
}
// This code is contributed by abhinavjain194

Python3

# Python3 program for the above approach
 
# Function to find the Bitwise OR
# of Bitwise AND of all subarrays
def findbitwiseOR(a, n):
     
    # Stores the required result
    res = 0
 
    # Generate all the subarrays
    for i in range(n):
         
        # Store the current element
        curr_sub_array = a[i]
 
        # Find the Bitwise OR
        res = res | curr_sub_array
 
        for j in range(i, n):
             
            # Update the result
            curr_sub_array = curr_sub_array & a[j]
            res = res | curr_sub_array
 
    # Print the result
    print (res)
 
# Driver Code
if __name__ == '__main__':
     
    A = [ 1, 2, 3 ]
    N = len(A)
     
    findbitwiseOR(A, N)
 
# This code is contributed by mohit kumar 29

C#

// C# program for the above approach
using System;
 
class GFG{
     
    // Function to find the Bitwise OR
    // of Bitwise AND of all subarrays
    static void findbitwiseOR(int[] a, int n)
    {
        // Stores the required result
        int res = 0;
  
        // Generate all the subarrays
        for (int i = 0; i < n; i++) {
  
            // Store the current element
            int curr_sub_array = a[i];
  
            // Find the Bitwise OR
            res = res | curr_sub_array;
  
            for (int j = i; j < n; j++) {
  
                // Update the result
                curr_sub_array = curr_sub_array & a[j];
                res = res | curr_sub_array;
            }
        }
  
        // Print the result
        Console.Write(res);
    }
 
// Driver code
static void Main()
{
    int[] A = { 1, 2, 3 };
        int N = A.Length;
        findbitwiseOR(A, N);
 
}
}
 
// This code is contributed by sanjoy_62.

Javascript

<script>
 
// JavaScript program for the above approach
 
    // Function to find the Bitwise OR
    // of Bitwise AND of all subarrays
    function findbitwiseOR(a, n)
    {
        // Stores the required result
        let res = 0;
 
        // Generate all the subarrays
        for (let i = 0; i < n; i++) {
 
            // Store the current element
            let curr_sub_array = a[i];
 
            // Find the Bitwise OR
            res = res | curr_sub_array;
 
            for (let j = i; j < n; j++) {
 
                // Update the result
                curr_sub_array = curr_sub_array & a[j];
                res = res | curr_sub_array;
            }
        }
 
        // Print the result
        document.write(res);
    }
 
// Driver Code
 
        let A = [ 1, 2, 3 ];
        let N = A.length;
        findbitwiseOR(A, N);
 
</script>  
Producción: 

3

 

Complejidad de Tiempo: O(N 2 )
Espacio Auxiliar: O(1)

Enfoque eficiente: el enfoque anterior también se puede optimizar en función de la observación de que el AND bit a bit de cualquier subarreglo siempre es menor o igual que el primer elemento del subarreglo. Por lo tanto, el valor máximo posible es Bitwise AND de los subarreglos son los elementos mismos. Por lo tanto, la tarea se reduce a encontrar el OR bit a bit de todos los elementos del arreglo como resultado.

A continuación se muestra la implementación del enfoque anterior:

C++

// C++ program for the above approach
 
#include <bits/stdc++.h>
using namespace std;
 
// Function to find the Bitwise OR of
// Bitwise AND of all consecutive
// subsets of the array
void findbitwiseOR(int* a, int n)
{
    // Stores the required result
    int res = 0;
 
    // Traverse the given array
    for (int i = 0; i < n; i++)
        res = res | a[i];
 
    // Print the result
    cout << res;
}
 
// Driver Code
int main()
{
    int A[] = { 1, 2, 3 };
    int N = sizeof(A) / sizeof(A[0]);
    findbitwiseOR(A, N);
 
    return 0;
}

Java

// Java program for the above approach
import java.io.*;
 
class GFG{
   
// Function to find the Bitwise OR of
// Bitwise AND of all consecutive
// subsets of the array
static void findbitwiseOR(int[] a, int n)
{
     
    // Stores the required result
    int res = 0;
 
    // Traverse the given array
    for(int i = 0; i < n; i++)
        res = res | a[i];
 
    // Print the result
    System.out.println(res);
}
 
// Driver Code
public static void main(String[] args)
{
    int[] A = { 1, 2, 3 };
    int N = A.length;
     
    findbitwiseOR(A, N);
}
}
 
// This code is contributed by Dharanendra L V.

Python3

# Python3 program for the above approach
 
# Function to find the Bitwise OR of
# Bitwise AND of all consecutive
# subsets of the array
def findbitwiseOR(a, n):
     
    # Stores the required result
    res = 0
 
    # Traverse the given array
    for i in range(n):
        res = res | a[i]
 
    # Print the result
    print(res)
 
# Driver Code
if __name__ == '__main__':
     
    A = [ 1, 2, 3 ]
    N = len(A)
     
    findbitwiseOR(A, N)
 
# This code is contributed by ipg2016107

C#

// C# program for the above approach
using System;
 
class GFG{
 
// Function to find the Bitwise OR of
// Bitwise AND of all consecutive
// subsets of the array
static void findbitwiseOR(int[] a, int n)
{
     
    // Stores the required result
    int res = 0;
 
    // Traverse the given array
    for(int i = 0; i < n; i++)
        res = res | a[i];
 
    // Print the result
    Console.Write(res);
}
 
// Driver Code
public static void Main()
{
    int[] A = { 1, 2, 3 };
    int N = A.Length;
     
    findbitwiseOR(A, N);
}
}
 
// This code is contributed by ukasp

Javascript

<script>
 
// JavaScript program for the above approach
 
// Function to find the Bitwise OR of
// Bitwise AND of all consecutive
// subsets of the array
function findbitwiseOR(a, n)
{
    // Stores the required result
    var res = 0;
     
    var i;
    // Traverse the given array
    for (i = 0; i < n; i++)
        res = res | a[i];
 
    // Print the result
    document.write(res);
}
 
// Driver Code
    var A = [1, 2, 3];
    var N = A.length;
    findbitwiseOR(A, N);
     
</script>
Producción: 

3

 

Complejidad temporal: O(N)
Espacio auxiliar: O(1)

Publicación traducida automáticamente

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