Dada una array arr[] que consta de N enteros no negativos, la tarea es contar el número de formas de dividir la array en tres subarreglos no vacíos diferentes , de modo que Bitwise XOR de cada subarreglo sea igual.
Ejemplos:
Entrada: arr[] = {7, 0, 5, 2, 7}
Salida: 2
Explicación: Todas las formas posibles son:
{{7}, {0, 5, 2}, {7}} donde el valor XOR de cada subarreglo es 7
{{7, 0}, {5, 2}, {7}} donde el valor XOR de cada subarreglo es 7Entrada: arr[] = {3, 1, 4}
Salida: 0
Enfoque ingenuo: el enfoque más simple es dividir la array en tres subarreglos no vacíos usando tres bucles y verificar si el XOR de cada subarreglo es igual o no. Si la condición dada se cumple, aumente el recuento final. Imprime el conteo final obtenido.
Complejidad de Tiempo: O(N 3 )
Espacio Auxiliar: O(1)
Enfoque eficiente: el enfoque anterior se puede optimizar en función de las siguientes observaciones:
- Sea xor_arr el XOR de todos los elementos del arreglo arr[] .
- Si arr[] se puede dividir en tres subarreglos diferentes de valores XOR iguales, entonces el XOR de todos los elementos en cada subarreglo será igual a xor_arr .
- Entonces, la idea es encontrar todas las arrays de prefijos y sufijos con un valor XOR igual a xor_arr .
- Si la longitud total de tal conjunto de prefijos y sufijos es menor que N, entonces existe otro subarreglo entre ellos con un valor XOR igual a xor_arr .
Por lo tanto, cuente el número total de todas las arrays de prefijos y sufijos que satisfacen la condición anterior. Siga los pasos a continuación para resolver el problema dado:
- Almacene el XOR de todos los elementos de la array , arr[] en una variable xor_arr .
- Cree una array , pref_ind[] para almacenar los puntos finales de cada array de prefijos cuyo valor XOR sea igual a xor_arr .
- Atraviese la array , arr[] e inserte los puntos finales de cada array de prefijos cuyo valor XOR sea igual a xor_arr en pref_ind .
- Cree otra array, suff_inds[] de tamaño N , donde suff_inds[i] almacena el número total de arrays de sufijos con un valor XOR igual a xor_arr cuyo punto de partida es mayor o igual que i .
- Atraviese la array , arr[] en orden inverso para llenar la array suff_inds[] . Si el valor XOR de la array de sufijos actual es igual a xor_arr , aumente suff_inds[i] en 1 . Además, agregue el valor de suff_inds[i+1] a suff_inds[i] .
- Para cada elemento idx en pref_ind si el valor de idx < N-1 , agregue el valor de suff_inds[idx + 2] al recuento final.
- Finalmente, imprima el valor del conteo final 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 ways to split array
// into three subarrays with equal Bitwise XOR
int countWays(int arr[], int N)
{
// Stores the XOR value of arr[]
int arr_xor = 0;
// Update the value of arr_xor
for (int i = 0; i < N; i++)
arr_xor ^= arr[i];
// Stores the XOR value of prefix
// and suffix array respectively
int pref_xor = 0, suff_xor = 0;
// Stores the ending points of all
// the required prefix arrays
vector<int> pref_ind;
// Stores the count of suffix arrays
// whose XOR value is equal to the
// total XOR value at each index
int suff_inds[N + 1];
memset(suff_inds, 0, sizeof suff_inds);
// Find all prefix arrays with
// XOR value equal to arr_xor
for (int i = 0; i < N; i++) {
// Update pref_xor
pref_xor ^= arr[i];
if (pref_xor == arr_xor)
pref_ind.push_back(i);
}
// Fill the values of suff_inds[]
for (int i = N - 1; i >= 0; i--) {
// Update suff_xor
suff_xor ^= arr[i];
// Update suff_inds[i]
suff_inds[i] += suff_inds[i + 1];
if (suff_xor == arr_xor)
suff_inds[i]++;
}
// Stores the total number of ways
int tot_ways = 0;
// Count total number of ways
for (int idx : pref_ind) {
if (idx < N - 1)
tot_ways += suff_inds[idx + 2];
}
// Return the final count
return tot_ways;
}
// Driver Code
int main()
{
// Given Input
int arr[] = { 7, 0, 5, 2, 7 };
int N = sizeof(arr) / sizeof(arr[0]);
// Function Call
cout << countWays(arr, N);
return 0;
}
Java
// Java program for the above approach
import java.lang.*;
import java.util.*;
class GFG
{
// Function to count ways to split array
// into three subarrays with equal Bitwise XOR
static int countWays(int arr[], int N)
{
// Stores the XOR value of arr[]
int arr_xor = 0;
// Update the value of arr_xor
for (int i = 0; i < N; i++)
arr_xor ^= arr[i];
// Stores the XOR value of prefix
// and suffix array respectively
int pref_xor = 0, suff_xor = 0;
// Stores the ending points of all
// the required prefix arrays
ArrayList<Integer> pref_ind=new ArrayList<>();
// Stores the count of suffix arrays
// whose XOR value is equal to the
// total XOR value at each index
int[] suff_inds= new int[N + 1];
// Find all prefix arrays with
// XOR value equal to arr_xor
for (int i = 0; i < N; i++) {
// Update pref_xor
pref_xor ^= arr[i];
if (pref_xor == arr_xor)
pref_ind.add(i);
}
// Fill the values of suff_inds[]
for (int i = N - 1; i >= 0; i--) {
// Update suff_xor
suff_xor ^= arr[i];
// Update suff_inds[i]
suff_inds[i] += suff_inds[i + 1];
if (suff_xor == arr_xor)
suff_inds[i]++;
}
// Stores the total number of ways
int tot_ways = 0;
// Count total number of ways
for (Integer idx : pref_ind) {
if (idx < N - 1)
tot_ways += suff_inds[idx + 2];
}
// Return the final count
return tot_ways;
}
// Driver code
public static void main(String[] args)
{
// Given Input
int arr[] = { 7, 0, 5, 2, 7 };
int N = arr.length;
// Function Call
System.out.println(countWays(arr, N));
}
}
// This code is contributed by offbeat
Python3
# Python3 program for the above approach # Function to count ways to split array # into three subarrays with equal Bitwise XOR def countWays(arr, N): # Stores the XOR value of arr[] arr_xor = 0 # Update the value of arr_xor for i in range(N): arr_xor ^= arr[i] # Stores the XOR value of prefix # and suffix array respectively pref_xor, suff_xor = 0, 0 # Stores the ending points of all # the required prefix arrays pref_ind = [] # Stores the count of suffix arrays # whose XOR value is equal to the # total XOR value at each index suff_inds = [0] * (N + 1) # memset(suff_inds, 0, sizeof suff_inds) # Find all prefix arrays with # XOR value equal to arr_xor for i in range(N): # Update pref_xor pref_xor ^= arr[i] if (pref_xor == arr_xor): pref_ind.append(i) # Fill the values of suff_inds[] for i in range(N - 1, -1, -1): # Update suff_xor suff_xor ^= arr[i] # Update suff_inds[i] suff_inds[i] += suff_inds[i + 1] if (suff_xor == arr_xor): suff_inds[i] += 1 # Stores the total number of ways tot_ways = 0 # Count total number of ways for idx in pref_ind: if (idx < N - 1): tot_ways += suff_inds[idx + 2] # Return the final count return tot_ways # Driver Code if __name__ == '__main__': # Given Input arr = [ 7, 0, 5, 2, 7 ] N = len(arr) # Function Call print (countWays(arr, N)) # This code is contributed by mohit kumar 29
C#
// C# program for the above approach
using System;
using System.Collections.Generic;
class GFG {
// Function to count ways to split array
// into three subarrays with equal Bitwise XOR
static int countWays(int[] arr, int N)
{
// Stores the XOR value of arr[]
int arr_xor = 0;
// Update the value of arr_xor
for (int i = 0; i < N; i++)
arr_xor ^= arr[i];
// Stores the XOR value of prefix
// and suffix array respectively
int pref_xor = 0, suff_xor = 0;
// Stores the ending points of all
// the required prefix arrays
List<int> pref_ind = new List<int>();
// Stores the count of suffix arrays
// whose XOR value is equal to the
// total XOR value at each index
int[] suff_inds = new int[N + 1];
// Find all prefix arrays with
// XOR value equal to arr_xor
for (int i = 0; i < N; i++) {
// Update pref_xor
pref_xor ^= arr[i];
if (pref_xor == arr_xor)
pref_ind.Add(i);
}
// Fill the values of suff_inds[]
for (int i = N - 1; i >= 0; i--) {
// Update suff_xor
suff_xor ^= arr[i];
// Update suff_inds[i]
suff_inds[i] += suff_inds[i + 1];
if (suff_xor == arr_xor)
suff_inds[i]++;
}
// Stores the total number of ways
int tot_ways = 0;
// Count total number of ways
foreach(int idx in pref_ind)
{
if (idx < N - 1)
tot_ways += suff_inds[idx + 2];
}
// Return the final count
return tot_ways;
}
// Driver code
public static void Main(string[] args)
{
// Given Input
int[] arr = { 7, 0, 5, 2, 7 };
int N = arr.Length;
// Function Call
Console.WriteLine(countWays(arr, N));
}
}
// This code is contributed by ukasp.
Javascript
<script>
// JavaScript program for the above approach
// Function to count ways to split array
// into three subarrays with equal Bitwise XOR
function countWays(arr, N)
{
// Stores the XOR value of arr[]
let arr_xor = 0;
// Update the value of arr_xor
for (let i = 0; i < N; i++)
arr_xor ^= arr[i];
// Stores the XOR value of prefix
// and suffix array respectively
let pref_xor = 0, suff_xor = 0;
// Stores the ending points of all
// the required prefix arrays
let pref_ind = [];
// Stores the count of suffix arrays
// whose XOR value is equal to the
// total XOR value at each index
let suff_inds = new Array(N + 1);
suff_inds.fill(0);
// Find all prefix arrays with
// XOR value equal to arr_xor
for (let i = 0; i < N; i++) {
// Update pref_xor
pref_xor ^= arr[i];
if (pref_xor == arr_xor)
pref_ind.push(i);
}
// Fill the values of suff_inds[]
for (let i = N - 1; i >= 0; i--) {
// Update suff_xor
suff_xor ^= arr[i];
// Update suff_inds[i]
suff_inds[i] += suff_inds[i + 1];
if (suff_xor == arr_xor)
suff_inds[i]++;
}
// Stores the total number of ways
let tot_ways = 0;
// Count total number of ways
for (let idx of pref_ind) {
if (idx < N - 1)
tot_ways += suff_inds[idx + 2];
}
// Return the final count
return tot_ways;
}
// Driver Code
// Given Input
let arr = [ 7, 0, 5, 2, 7 ];
let N = arr.length;
// Function Call
document.write(countWays(arr, N));
</script>
Producción:
2
Complejidad temporal: O(N)
Espacio auxiliar: O(N)
Publicación traducida automáticamente
Artículo escrito por kundudinesh007 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA