Dada una array arr[] de longitud N, , se definió una array de dimensiones N * N en la array arr[] donde M i, j = arr i & arr j . Dados cuatro enteros X, Y, S y T , la tarea es encontrar el XOR bit a bit de todos los elementos de la subarray desde la parte superior izquierda (X, Y) hasta la parte inferior derecha (S, T) .
Ejemplos:
Entrada: N = 3, A[] = {2, 3, 4}, (X, Y)=(0, 1), (S, T)=(2, 2)
Salida: 5
Explicación:
Array definida en A es
{{(2 y 2), (2 y 3), (2 y 4)},
{(3 y 2), (3 y 3), (3 y 4)},
{(4 y 2), (4 y 3), (4 y 4)}}Finalmente, la array será:
{{2, 2, 0},
{2, 3, 0},
{0, 0, 4}}
valor XOR = (2^0)^(3^0)^(0^ 4) = 5Entrada: N=3, A[]={1, 2, 3}, (X, Y)=(0, 1), (S, T)=(1, 2)
Salida: 1
Enfoque ingenuo: el enfoque más simple es generar la array M a partir de la array dada y calcular el XOR bit a bit de todos los elementos presentes en la subarray dada de M.
Tiempo Complejidad: O(N 2 )
Espacio Auxiliar: O(N 2 )
Enfoque eficiente: la idea es utilizar la siguiente propiedad distributiva de las operaciones ‘XOR’ y ‘AND’:
(A y B) ^ (A y C) = A y (B ^ C)
Por lo tanto, el XOR final de la subarray desde la parte superior izquierda (X, Y) hasta la parte inferior derecha (S, T) se puede calcular a partir de la siguiente ecuación:
XOR final
= (XOR de la fila X)^(XOR de la fila X+1)^. . . . ^(XOR de la fila S)
= (A X & (A Y ^. . . .^ A T )) ^ ….
. . . ^(A S & (A Y ^. . . .^A T ))
= (A Y ^. . . .^A T )&(A X ^. . .^A S )
- Itere sobre la array desde los índices Y hasta T y calcule el XOR de los elementos.
- Recorra la array desde los índices X a S y calcule el XOR de los elementos.
- Finalmente, calcule el AND bit a bit de los XOR calculados, que es igual al XOR bit a bit de la subarray de (X, Y) a (S, T)
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program of the
// above approach
#include <iostream>
using namespace std;
// Function to find the submatrix
// XOR of the given matrix
int submatrix_xor(int* A, int N,
int X, int Y,
int S, int T)
{
int left_xor = 0, i, right_xor = 0;
// Calculating left xor
// i.e A[Y]^A[Y+1]^. . .^A[T]
for (i = Y; i <= T; i++) {
left_xor ^= A[i];
}
// Calculating right xor
// i.e A[X]^A[X+1]^. . .^A[S]
for (i = X; i <= S; i++) {
right_xor ^= A[i];
}
// Bitwise AND of left_xor and
// right_xor gives required result
return left_xor & right_xor;
}
// Driver Code
int main()
{
int A[3] = { 2, 3, 4 }, X = 0,
Y = 1, S = 2, T = 2, N = 3;
// Printing xor of submatrix
cout << submatrix_xor(A, N, X,
Y, S, T);
return 0;
}
Java
// Java program of the
// above approach
import java.io.*;
class GFG{
// Function to find the submatrix
// XOR of the given matrix
static int submatrix_xor(int[] A, int N,
int X, int Y,
int S, int T)
{
int left_xor = 0, i, right_xor = 0;
// Calculating left xor
// i.e A[Y]^A[Y+1]^. . .^A[T]
for(i = Y; i <= T; i++)
{
left_xor ^= A[i];
}
// Calculating right xor
// i.e A[X]^A[X+1]^. . .^A[S]
for(i = X; i <= S; i++)
{
right_xor ^= A[i];
}
// Bitwise AND of left_xor and
// right_xor gives required result
return left_xor & right_xor;
}
// Driver Code
public static void main (String[] args)
{
int[] A = { 2, 3, 4 };
int X = 0, Y = 1, S = 2,
T = 2, N = 3;
// Printing xor of submatrix
System.out.print(submatrix_xor(A, N, X,
Y, S, T));
}
}
// This code is contributed by code_hunt
Python3
# Python3 program of the # above approach # Function to find the submatrix # XOR of the given matrix def submatrix_xor(A, N, X, Y, S, T): left_xor = 0 i = 0 right_xor = 0 # Calculating left xor # i.e A[Y]^A[Y+1]^. . .^A[T] for i in range(Y, T + 1): left_xor ^= A[i] # Calculating right xor # i.e A[X]^A[X+1]^. . .^A[S] for i in range(X, S + 1): right_xor ^= A[i] # Bitwise AND of left_xor and # right_xor gives required result return left_xor & right_xor # Driver Code if __name__ == '__main__': A = [ 2, 3, 4 ] X = 0 Y = 1 S = 2 T = 2 N = 3 # Printing xor of submatrix print(submatrix_xor(A, N, X, Y, S, T)) # This code is contributed by mohit kumar 29
C#
// C# program for the above approach
using System;
class GFG{
// Function to find the submatrix
// XOR of the given matrix
static int submatrix_xor(int[] A, int N,
int X, int Y,
int S, int T)
{
int left_xor = 0, i, right_xor = 0;
// Calculating left xor
// i.e A[Y]^A[Y+1]^. . .^A[T]
for(i = Y; i <= T; i++)
{
left_xor ^= A[i];
}
// Calculating right xor
// i.e A[X]^A[X+1]^. . .^A[S]
for(i = X; i <= S; i++)
{
right_xor ^= A[i];
}
// Bitwise AND of left_xor and
// right_xor gives required result
return left_xor & right_xor;
}
// Driver Code
public static void Main ()
{
int[] A = { 2, 3, 4 };
int X = 0, Y = 1, S = 2,
T = 2, N = 3;
// Printing xor of submatrix
Console.Write(submatrix_xor(A, N, X,
Y, S, T));
}
}
// This code is contributed by code_hunt
Javascript
<script>
// JavaScript program to implement
// the above approach
// Function to find the submatrix
// XOR of the given matrix
function submatrix_xor(A, N, X, Y, S, T)
{
let left_xor = 0, i, right_xor = 0;
// Calculating left xor
// i.e A[Y]^A[Y+1]^. . .^A[T]
for(i = Y; i <= T; i++)
{
left_xor ^= A[i];
}
// Calculating right xor
// i.e A[X]^A[X+1]^. . .^A[S]
for(i = X; i <= S; i++)
{
right_xor ^= A[i];
}
// Bitwise AND of left_xor and
// right_xor gives required result
return left_xor & right_xor;
}
// Driver code
let A = [ 2, 3, 4 ];
let X = 0, Y = 1, S = 2,
T = 2, N = 3;
// Printing xor of submatrix
document.write(submatrix_xor(A, N, X,
Y, S, T));
// This code is contributed by target_2.
</script>
5
Complejidad de tiempo: O(N), donde N es el tamaño de la array
Espacio auxiliar: O(1)
Publicación traducida automáticamente
Artículo escrito por ManikantaBandla y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA