Cuente los subarreglos que tienen incluso Bitwise OR

Dada una array arr[] que consta de N enteros positivos, la tarea es contar el número de subarreglos cuyo OR bit a bit de sus elementos es par.

Ejemplos:

Entrada: arr[] = {1, 5, 4, 2, 6 }
Salida: 6
Explicación:
Los subarreglos con OR bit a bit par son {4}, {2}, {6}, {2, 6}, {4, 2}, {4, 2, 6}.
Por lo tanto, el número de subarreglos que tienen incluso Bitwise OR es 6.

Entrada: arr[] ={2, 5, 6, 8}
Salida: 4

Enfoque ingenuo: el enfoque más simple para resolver el problema es generar todos los subarreglos y si el bit a bit OR de cualquier subarreglo es par , entonces aumente el conteo de dichos subarreglos. Después de verificar todos los subarreglos, imprima el conteo obtenido como resultado.

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

Enfoque eficiente: el enfoque anterior se puede optimizar al observar el hecho de que si alguno de los elementos en el subarreglo es impar , seguramente hará que el OR bit a bit del subarreglo sea impar. Por lo tanto, la idea es encontrar la longitud del segmento continuo en la array que es par y agregar su contribución a la cuenta total. 
Siga los pasos a continuación para resolver el problema:

  • Inicialice una variable, por ejemplo, count , para almacenar el número total de subarreglos que tengan OR bit a bit como pares.
  • Inicialice una variable, digamos L , para almacenar el recuento de elementos adyacentes que son pares.
  • Recorra la array dada arr[] y realice los siguientes pasos:
    • Si el elemento actual es par entonces, incremente el valor de L en 1 .
    • De lo contrario, agregue el valor L * (L + 1) / 2 a la variable conteo y actualice L a 0 .
  • Si el valor de L es distinto de cero, agregue L*(L + 1)/2 a la variable count .
  • Después de completar los pasos anteriores, imprima el valor de conteo 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 count the number of
// subarrays having even Bitwise OR
int bitOr(int arr[], int N)
{
    // Store number of subarrays
    // having even bitwise OR
    int count = 0;
 
    // Store the length of the current
    // subarray having even numbers
    int length = 0;
 
    // Traverse the array
    for (int i = 0; i < N; i++) {
 
        // If the element is even
        if (arr[i] % 2 == 0) {
 
            // Increment size of the
            // current continuous sequence
// of even array elements
            length++;
        }
 
        // If arr[i] is odd
        else {
 
            // If length is non zero
            if (length != 0) {
 
                // Adding contribution of
                // subarrays consisting
                // only of even numbers
                count += ((length)
                          * (length + 1))
                         / 2;
            }
 
            // Make length of subarray as 0
            length = 0;
        }
    }
 
    // Add contribution of previous subarray
    count += ((length) * (length + 1)) / 2;
 
    // Return total count of subarrays
    return count;
}
 
// Driver Code
int main()
{
    int arr[] = { 1, 5, 4, 2, 6 };
    int N = sizeof(arr) / sizeof(arr[0]);
 
    // Function Call
    cout << bitOr(arr, N);
 
    return 0;
}

Java

// Java program for the above approach
import java.util.*;
 
class GFG{
     
// Function to count the number of
// subarrays having even Bitwise OR
static int bitOr(int arr[], int N)
{
     
    // Store number of subarrays
    // having even bitwise OR
    int count = 0;
 
    // Store the length of the current
    // subarray having even numbers
    int length = 0;
 
    // Traverse the array
    for(int i = 0; i < N; i++)
    {
         
        // If the element is even
        if (arr[i] % 2 == 0)
        {
             
            // Increment size of the
            // current continuous sequence
            // of even array elements
            length++;
        }
 
        // If arr[i] is odd
        else
        {
             
            // If length is non zero
            if (length != 0)
            {
                 
                // Adding contribution of
                // subarrays consisting
                // only of even numbers
                count += ((length) * (length + 1)) / 2;
            }
 
            // Make length of subarray as 0
            length = 0;
        }
    }
 
    // Add contribution of previous subarray
    count += ((length) * (length + 1)) / 2;
 
    // Return total count of subarrays
    return count;
}
 
// Driver Code
public static void main(String[] args)
{
    int arr[] = { 1, 5, 4, 2, 6 };
    int N = arr.length;
 
    // Function Call
    System.out.print(bitOr(arr, N));
}
}
 
// This code is contributed by splevel62

Python3

# Python3 program for the above approach
 
# Function to count the number of
# subarrays having even Bitwise OR
def bitOr(arr, N):
     
    # Store number of subarrays
    # having even bitwise OR
    count = 0
 
    # Store the length of the current
    # subarray having even numbers
    length = 0
 
    # Traverse the array
    for i in range(N):
 
        # If the element is even
        if (arr[i] % 2 == 0):
 
            # Increment size of the
            # current continuous sequence
            # of even array elements
            length += 1
             
        # If arr[i] is odd
        else:
             
            # If length is non zero
            if (length != 0):
 
                # Adding contribution of
                # subarrays consisting
                # only of even numbers
                count += ((length) * (length + 1)) // 2
 
            # Make length of subarray as 0
            length = 0
 
    # Add contribution of previous subarray
    count += ((length) * (length + 1)) // 2
 
    # Return total count of subarrays
    return count
 
# Driver Code
if __name__ == '__main__':
     
    arr = [ 1, 5, 4, 2, 6 ]
    N = len(arr)
 
    # Function Call
    print (bitOr(arr, N))
 
# This code is contributed by mohit kumar 29

C#

// C# program for the above approach
using System;
class GFG
{
 
  // Function to count the number of
  // subarrays having even Bitwise OR
  static int bitOr(int[] arr, int N)
  {
 
    // Store number of subarrays
    // having even bitwise OR
    int count = 0;
 
    // Store the length of the current
    // subarray having even numbers
    int length = 0;
 
    // Traverse the array
    for(int i = 0; i < N; i++)
    {
 
      // If the element is even
      if (arr[i] % 2 == 0)
      {
 
        // Increment size of the
        // current continuous sequence
        // of even array elements
        length++;
      }
 
      // If arr[i] is odd
      else
      {
 
        // If length is non zero
        if (length != 0)
        {
 
          // Adding contribution of
          // subarrays consisting
          // only of even numbers
          count += ((length) * (length + 1)) / 2;
        }
 
        // Make length of subarray as 0
        length = 0;
      }
    }
 
    // Add contribution of previous subarray
    count += ((length) * (length + 1)) / 2;
 
    // Return total count of subarrays
    return count;
  }
 
  // Driver code
  static void Main()
  {
    int[] arr = { 1, 5, 4, 2, 6 };
    int N = arr.Length;
 
    // Function Call
    Console.Write(bitOr(arr, N));
  }
}
 
// This code is contributed by sanjoy_62.

Javascript

<script>
 
// Javascript program for the above approach
 
// Function to count the number of
// subarrays having even Bitwise OR
function bitOr(arr, N)
{
    // Store number of subarrays
    // having even bitwise OR
    var count = 0;
 
    // Store the length of the current
    // subarray having even numbers
    var length = 0;
    var i;
 
    // Traverse the array
    for (i = 0; i < N; i++) {
 
        // If the element is even
        if (arr[i] % 2 == 0) {
 
            // Increment size of the
            // current continuous sequence
// of even array elements
            length++;
        }
 
        // If arr[i] is odd
        else {
 
            // If length is non zero
            if (length != 0) {
 
                // Adding contribution of
                // subarrays consisting
                // only of even numbers
                count += Math.floor((length)
                          * (length + 1)
                         / 2);
            }
 
            // Make length of subarray as 0
            length = 0;
        }
    }
 
    // Add contribution of previous subarray
    count += Math.floor((length) * (length + 1) / 2);
 
    // Return total count of subarrays
    return count;
}
 
// Driver Code
 
    var arr = [1, 5, 4, 2, 6]
    var N = arr.length;
 
    // Function Call
    document.write(bitOr(arr, N));
 
</script>
Producción: 

6

 

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

Publicación traducida automáticamente

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