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