Dada una array arr[] de tamaño N , la tarea es contar el número de subarreglos de la array dada que tienen un valor XOR bit a bit impar .
Ejemplos:
Entrada: arr[] = {1, 4, 7, 9, 10}
Salida: 8
Explicación: Los subarreglos que tienen XOR bit a bit impar son {1}, {1, 4}, {1, 4, 7, 9}, { 1, 4, 7, 9, 10}, {7}, {9}, {4, 7}, {9, 10}.Entrada: arr[] ={1, 5, 6}
Salida: 3
Explicación: Los subarreglos que tienen XOR bit a bit impar son {1}, {1, 5}, {1, 5, 6}.
Enfoque ingenuo: el enfoque más simple para resolver este problema es verificar para cada subarreglo si su Bitwise XOR es impar o no. Si se encuentra impar, entonces aumente el conteo. Finalmente, imprima el conteo como resultado.
Complejidad de Tiempo: O(N 2 )
Espacio Auxiliar: O(1)
Enfoque eficiente: para optimizar el enfoque anterior, la idea se basa en la observación de que el XOR bit a bit del subarreglo es impar solo si la cantidad de elementos impares en ese subarreglo es impar. Para resolver el problema, encuentre el número de subarreglos a partir del índice 0 y que satisfagan las condiciones dadas. Luego, recorra la array y actualice la cantidad de subarreglos que comienzan en el índice i que satisfacen la condición dada. Siga los pasos a continuación para resolver el problema:
- Inicialice las variables Odd , C_odd como 0 , para almacenar el número de números impares hasta el i -ésimo índice y el número de subarreglos requeridos comenzando en el i -ésimo índice respectivamente.
- Recorra la array arr[] usando la variable i y verifique los siguientes pasos:
- Si el valor de arr[i] es impar , actualice el valor de Odd a !Odd .
- Si el valor de Odd no es cero , incremente C_odd en 1 .
- Nuevamente, recorra la array arr[] usando la variable i y realice lo siguiente:
- Agregue el valor de C_odd a una variable res .
- Si el valor de arr[i] es impar , actualice el valor de C_odd a (N – i – C_odd) .
- Después de completar los pasos anteriores, imprima el valor de res 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
// of the given array having odd Bitwise XOR
void oddXorSubarray(int a[], int n)
{
// Stores number of odd
// numbers upto i-th index
int odd = 0;
// Stores number of required
// subarrays starting from i-th index
int c_odd = 0;
// Store the required result
int result = 0;
// Find the number of subarrays having odd
// Bitwise XOR values starting at 0-th index
for (int i = 0; i < n; i++) {
// Check if current element is odd
if (a[i] & 1) {
odd = !odd;
}
// If the current value of odd is not
// zero, increment c_odd by 1
if (odd) {
c_odd++;
}
}
// Find the number of subarrays having odd
// bitwise XOR value starting at ith index
// and add to result
for (int i = 0; i < n; i++) {
// Add c_odd to result
result += c_odd;
if (a[i] & 1) {
c_odd = (n - i - c_odd);
}
}
// Print the result
cout << result;
}
// Driver Code
int main()
{
// Given array
int arr[] = { 1, 4, 7, 9, 10 };
// Stores the size of the array
int N = sizeof(arr) / sizeof(arr[0]);
oddXorSubarray(arr, N);
return 0;
}
Java
// Java program for the above approach
import java.io.*;
class GFG
{
// Function to count the number of subarrays
// of the given array having odd Bitwise XOR
static void oddXorSubarray(int a[], int n)
{
// Stores number of odd
// numbers upto i-th index
int odd = 0;
// Stores number of required
// subarrays starting from i-th index
int c_odd = 0;
// Store the required result
int result = 0;
// Find the number of subarrays having odd
// Bitwise XOR values starting at 0-th index
for (int i = 0; i < n; i++)
{
// Check if current element is odd
if (a[i] % 2 != 0)
{
odd = (odd == 0) ? 1 : 0;
}
// If the current value of odd is not
// zero, increment c_odd by 1
if (odd != 0)
{
c_odd++;
}
}
// Find the number of subarrays having odd
// bitwise XOR value starting at ith index
// and add to result
for (int i = 0; i < n; i++)
{
// Add c_odd to result
result += c_odd;
if (a[i] % 2 != 0)
{
c_odd = (n - i - c_odd);
}
}
// Print the result
System.out.println(result);
}
// Driver Code
public static void main (String[] args)
{
// Given array
int arr[] = { 1, 4, 7, 9, 10 };
// Stores the size of the array
int N = arr.length;
oddXorSubarray(arr, N);
}
}
// This code is contributed by Dharanendra L V.
Python3
# Python3 program for the above approach # Function to count the number of subarrays # of the given array having odd Bitwise XOR def oddXorSubarray(a, n): # Stores number of odd # numbers upto i-th index odd = 0 # Stores number of required # subarrays starting from i-th index c_odd = 0 # Store the required result result = 0 # Find the number of subarrays having odd # Bitwise XOR values starting at 0-th index for i in range(n): # Check if current element is odd if (a[i] & 1): odd = not odd # If the current value of odd is not # zero, increment c_odd by 1 if (odd): c_odd += 1 # Find the number of subarrays having odd # bitwise XOR value starting at ith index # and add to result for i in range(n): # Add c_odd to result result += c_odd if (a[i] & 1): c_odd = (n - i - c_odd) # Print the result print (result) # Driver Code if __name__ == '__main__': # Given array arr = [1, 4, 7, 9, 10] # Stores the size of the array N = len(arr) oddXorSubarray(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
// of the given array having odd Bitwise XOR
static void oddXorSubarray(int []a, int n)
{
// Stores number of odd
// numbers upto i-th index
int odd = 0;
// Stores number of required
// subarrays starting from i-th index
int c_odd = 0;
// Store the required result
int result = 0;
// Find the number of subarrays having
// odd Bitwise XOR values starting at
// 0-th index
for(int i = 0; i < n; i++)
{
// Check if current element is odd
if (a[i] % 2 != 0)
{
odd = (odd == 0) ? 1 : 0;
}
// If the current value of odd is not
// zero, increment c_odd by 1
if (odd != 0)
{
c_odd++;
}
}
// Find the number of subarrays having odd
// bitwise XOR value starting at ith index
// and add to result
for(int i = 0; i < n; i++)
{
// Add c_odd to result
result += c_odd;
if (a[i] % 2 != 0)
{
c_odd = (n - i - c_odd);
}
}
// Print the result
Console.WriteLine(result);
}
// Driver Code
public static void Main(String[] args)
{
// Given array
int []arr = { 1, 4, 7, 9, 10 };
// Stores the size of the array
int N = arr.Length;
oddXorSubarray(arr, N);
}
}
// This code is contributed by 29AjayKumar
Javascript
<script>
// javascript program for the above approach
// Function to count the number of subarrays
// of the given array having odd Bitwise XOR
function oddXorSubarray(a , n) {
// Stores number of odd
// numbers upto i-th index
var odd = 0;
// Stores number of required
// subarrays starting from i-th index
var c_odd = 0;
// Store the required result
var result = 0;
// Find the number of subarrays having odd
// Bitwise XOR values starting at 0-th index
for (i = 0; i < n; i++) {
// Check if current element is odd
if (a[i] % 2 != 0) {
odd = (odd == 0) ? 1 : 0;
}
// If the current value of odd is not
// zero, increment c_odd by 1
if (odd != 0) {
c_odd++;
}
}
// Find the number of subarrays having odd
// bitwise XOR value starting at ith index
// and add to result
for (i = 0; i < n; i++) {
// Add c_odd to result
result += c_odd;
if (a[i] % 2 != 0) {
c_odd = (n - i - c_odd);
}
}
// Print the result
document.write(result);
}
// Driver Code
// Given array
var arr = [ 1, 4, 7, 9, 10 ];
// Stores the size of the array
var N = arr.length;
oddXorSubarray(arr, N);
// This code contributed by Rajput-Ji
</script>
Producción:
8
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