Problema Dada una array cuadrada de lado N tenemos que encontrar una subarray tal que el XOR bit a bit de sus elementos sea máximo, y tenemos que imprimir el XOR bit a bit máximo.
Ejemplos:
Input :
matrix is
{ {1, 2, 3, 4}
{5, 6, 7, 8}
{9, 10, 11, 12}
{13, 14, 15, 16} }
Output : 31
We get the value 31 by doing XOR of submatrix [15, 16}
Enfoque ingenuo El enfoque de fuerza bruta es encontrar toda la subarray de la array ejecutando cuatro bucles, dos para la fila y la columna iniciales y dos para la fila y la columna finales y ahora encontrar el xor de todos los elementos de la subarray y descubrir el xor y comprobar si el xor de esta subarray es máximo o no.
Complejidad de tiempo: O (n^6)
Enfoque eficiente En este enfoque, calcularemos el xor de cada subarray desde 1, 1 hasta i, j, esto se puede hacer en O (N*N) usando esta fórmula
(xor de subarray de 1, 1 a i, j ) = (xor de subarray de 1, 1 a i-1, j )^(xor de subarray de 1, 1 a i, j-1) ^ (xor de subarray de 1, 1 a i-1, j-1) ^ arr[i][j] .
Ahora, para calcular xor de la subarray desde i, j hasta i1, j1, podemos usar la siguiente fórmula
(xor de subarray de i, j a i1, j1) = (xor de subarray de 1, 1 a i1, j1 )^(xor de subarray de 1, 1 a i-1, j-1) ^ (xor de subarray de 1, 1 a i1, j-1) ^ (xor de subarray de 1, 1 a i-1, j1).
tenemos que ejecutar cuatro bucles para encontrar toda la subarray de la array y el xor de la subarray se puede calcular en tiempo O (1).
Entonces la complejidad del tiempo se reduce a O(N^4)
C++
// C++ program to implement the above approach
#include <bits/stdc++.h>
using namespace std;
#define N 101
// Compute the xor of elements from (1, 1) to
// (i, j) and store it in prefix_xor[i][j]
void prefix(int arr[N][N], int prefix_xor[N][N], int n)
{
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= n; j++) {
// xor of submatrix from 1, 1 to i, j is
// (xor of submatrix from 1, 1 to i-1,
// j )^(xor of submatrix from 1, 1 to i, j-1)
// ^(xor of submatrix from 1, 1 to i-1, j-1) ^
// arr[i][j]
prefix_xor[i][j] = arr[i][j] ^
prefix_xor[i - 1][j] ^
prefix_xor[i][j - 1] ^
prefix_xor[i - 1][j - 1];
}
}
}
// find the submatrix with maximum xor value
void Max_xor(int prefix_xor[N][N], int n)
{
int max_value = 0;
// we need four loops to find all the submatrix
// of a matrix
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= n; j++) {
for (int i1 = i; i1 <= n; i1++) {
for (int j1 = j; j1 <= n; j1++) {
// xor of submatrix from i, j to i1, j1 is
// (xor of submatrix from 1, 1 to i1, j1 )
// ^(xor of submatrix from 1, 1 to i-1, j-1)
// ^(xor of submatrix from 1, 1 to i1, j-1)
// ^(xor of submatrix from 1, 1 to i-1, j1)
int x = 0;
x ^= prefix_xor[i1][j1];
x ^= prefix_xor[i - 1][j - 1];
x ^= prefix_xor[i1][j - 1];
x ^= prefix_xor[i - 1][j1];
// if the xor is greater than maximum value
// substitute it
max_value = max(max_value, x);
}
}
}
}
cout << max_value << endl;
}
// Driver code
int main()
{
int arr[N][N] = { { 1, 2, 3, 4 },
{ 5, 6, 7, 8 },
{ 9, 10, 11, 12 },
{ 13, 14, 15, 16 } };
int n = 4;
int prefix_xor[N][N] = { 0 };
// Find the prefix_xor
prefix(arr, prefix_xor, n);
// Find submatrix with maximum bitwise xor
Max_xor(prefix_xor, n);
return 0;
}
Java
// Java program to implement the above approach
public class GFG
{
static int N =101;
// Compute the xor of elements from (1, 1) to
// (i, j) and store it in prefix_xor[i][j]
static void prefix(int arr[][], int prefix_xor[][], int n)
{
for (int i = 1; i < n; i++)
{
for (int j = 1; j < n; j++)
{
// xor of submatrix from 1, 1 to i, j is
// (xor of submatrix from 1, 1 to i-1,
// j )^(xor of submatrix from 1, 1 to i, j-1)
// ^(xor of submatrix from 1, 1 to i-1, j-1) ^
// arr[i][j]
prefix_xor[i][j] = arr[i][j] ^
prefix_xor[i - 1][j] ^
prefix_xor[i][j - 1] ^
prefix_xor[i - 1][j - 1];
}
}
}
// find the submatrix with maximum xor value
static void Max_xor(int prefix_xor[][], int n)
{
int max_value = 0;
// we need four loops to find all the submatrix
// of a matrix
for (int i = 1; i <= n; i++)
{
for (int j = 1; j <= n; j++)
{
for (int i1 = i; i1 <= n; i1++)
{
for (int j1 = j; j1 <= n; j1++)
{
// xor of submatrix from i, j to i1, j1 is
// (xor of submatrix from 1, 1 to i1, j1 )
// ^(xor of submatrix from 1, 1 to i-1, j-1)
// ^(xor of submatrix from 1, 1 to i1, j-1)
// ^(xor of submatrix from 1, 1 to i-1, j1)
int x = 0;
x ^= prefix_xor[i1][j1];
x ^= prefix_xor[i - 1][j - 1];
x ^= prefix_xor[i1][j - 1];
x ^= prefix_xor[i - 1][j1];
// if the xor is greater than maximum value
// substitute it
max_value = Math.max(max_value, x);
}
}
}
}
System.out.println(max_value);
}
// Driver code
public static void main(String[] args)
{
int arr[][] = { { 1, 2, 3, 4 },
{ 5, 6, 7, 8 },
{ 9, 10, 11, 12 },
{ 13, 14, 15, 16 } };
int n = 4;
int prefix_xor[][] = new int[N][N];
// Find the prefix_xor
prefix(arr, prefix_xor, n);
// Find submatrix with maximum bitwise xor
Max_xor(prefix_xor, n);
}
}
// This code is contributed by 29AjayKumar
Python3
# Python3 program to implement the above approach N = 101 # Compute the xor of elements from (1, 1) to # (i, j) and store it in prefix_xor[i][j] def prefix(arr, prefix_xor, n): for i in range(1, n): for j in range(1, n): # xor of submatrix from 1, 1 to i, j is # (xor of submatrix from 1, 1 to i-1, # j )^(xor of submatrix from 1, 1 to i, j-1) # ^(xor of submatrix from 1, 1 to i-1, j-1) ^ # arr[i][j] prefix_xor[i][j] = (arr[i][j] ^ prefix_xor[i - 1][j] ^ prefix_xor[i][j - 1] ^ prefix_xor[i - 1][j - 1]) # find the submatrix with maximum xor value def Max_xor(prefix_xor, n): max_value = 0 # we need four loops to find # all the submatrix of a matrix for i in range(1, n + 1): for j in range(1, n + 1): for i1 in range(i, n + 1): for j1 in range(j, n + 1): # xor of submatrix from i, j to i1, j1 is # (xor of submatrix from 1, 1 to i1, j1 ) # ^(xor of submatrix from 1, 1 to i-1, j-1) # ^(xor of submatrix from 1, 1 to i1, j-1) # ^(xor of submatrix from 1, 1 to i-1, j1) x = 0 x ^= prefix_xor[i1][j1] x ^= prefix_xor[i - 1][j - 1] x ^= prefix_xor[i1][j - 1] x ^= prefix_xor[i - 1][j1] # if the xor is greater than maximum value # substitute it max_value = max(max_value, x) print(max_value) # Driver code arr = [[ 1, 2, 3, 4 ], [ 5, 6, 7, 8 ], [ 9, 10, 11, 12 ], [ 13, 14, 15, 16 ]] n = 4 prefix_xor = [[ 0 for i in range(N)] for i in range(N)] # Find the prefix_xor prefix(arr, prefix_xor, n) # Find submatrix with maximum bitwise xor Max_xor(prefix_xor, n) # This code is contributed by Mohit Kumar
C#
// C# program to implement the above approach
using System;
using System.Collections.Generic;
public class GFG
{
static int N =101;
// Compute the xor of elements from (1, 1) to
// (i, j) and store it in prefix_xor[i,j]
static void prefix(int [,]arr, int [,]prefix_xor, int n)
{
for (int i = 1; i < n; i++)
{
for (int j = 1; j < n; j++)
{
// xor of submatrix from 1, 1 to i, j is
// (xor of submatrix from 1, 1 to i-1,
// j )^(xor of submatrix from 1, 1 to i, j-1)
// ^(xor of submatrix from 1, 1 to i-1, j-1) ^
// arr[i,j]
prefix_xor[i,j] = arr[i,j] ^
prefix_xor[i - 1,j] ^
prefix_xor[i,j - 1] ^
prefix_xor[i - 1,j - 1];
}
}
}
// find the submatrix with maximum xor value
static void Max_xor(int [,]prefix_xor, int n)
{
int max_value = 0;
// we need four loops to find all the submatrix
// of a matrix
for (int i = 1; i <= n; i++)
{
for (int j = 1; j <= n; j++)
{
for (int i1 = i; i1 <= n; i1++)
{
for (int j1 = j; j1 <= n; j1++)
{
// xor of submatrix from i, j to i1, j1 is
// (xor of submatrix from 1, 1 to i1, j1 )
// ^(xor of submatrix from 1, 1 to i-1, j-1)
// ^(xor of submatrix from 1, 1 to i1, j-1)
// ^(xor of submatrix from 1, 1 to i-1, j1)
int x = 0;
x ^= prefix_xor[i1, j1];
x ^= prefix_xor[i - 1, j - 1];
x ^= prefix_xor[i1, j - 1];
x ^= prefix_xor[i - 1, j1];
// if the xor is greater than maximum value
// substitute it
max_value = Math.Max(max_value, x);
}
}
}
}
Console.WriteLine(max_value);
}
// Driver code
public static void Main(String[] args)
{
int [,]arr = { { 1, 2, 3, 4 },
{ 5, 6, 7, 8 },
{ 9, 10, 11, 12 },
{ 13, 14, 15, 16 } };
int n = 4;
int [,]prefix_xor = new int[N,N];
// Find the prefix_xor
prefix(arr, prefix_xor, n);
// Find submatrix with maximum bitwise xor
Max_xor(prefix_xor, n);
}
}
// This code is contributed by 29AjayKumar
Javascript
<script>
// Javascript program to implement the above approach
var N = 101;
// Compute the xor of elements from (1, 1) to
// (i, j) and store it in prefix_xor[i][j]
function prefix(arr, prefix_xor, n)
{
for (var i = 1; i < n; i++) {
for (var j = 1; j < n; j++) {
// xor of submatrix from 1, 1 to i, j is
// (xor of submatrix from 1, 1 to i-1,
// j )^(xor of submatrix from 1, 1 to i, j-1)
// ^(xor of submatrix from 1, 1 to i-1, j-1) ^
// arr[i][j]
prefix_xor[i][j] = arr[i][j] ^
prefix_xor[i - 1][j] ^
prefix_xor[i][j - 1] ^
prefix_xor[i - 1][j - 1];
}
}
}
// find the submatrix with maximum xor value
function Max_xor(prefix_xor, n)
{
var max_value = 0;
// we need four loops to find all the submatrix
// of a matrix
for (var i = 1; i <= n; i++)
{
for (var j = 1; j <= n; j++)
{
for (var i1 = i; i1 <= n; i1++)
{
for (var j1 = j; j1 <= n; j1++)
{
// xor of submatrix from i, j to i1, j1 is
// (xor of submatrix from 1, 1 to i1, j1 )
// ^(xor of submatrix from 1, 1 to i-1, j-1)
// ^(xor of submatrix from 1, 1 to i1, j-1)
// ^(xor of submatrix from 1, 1 to i-1, j1)
var x = 0;
x ^= prefix_xor[i1][j1];
x ^= prefix_xor[i - 1][j - 1];
x ^= prefix_xor[i1][j - 1];
x ^= prefix_xor[i - 1][j1];
// if the xor is greater than maximum value
// substitute it
max_value = Math.max(max_value, x);
}
}
}
}
document.write( max_value );
}
// Driver code
var arr = [ [ 1, 2, 3, 4 ],
[ 5, 6, 7, 8 ],
[ 9, 10, 11, 12 ],
[ 13, 14, 15, 16 ] ];
var n = 4;
var prefix_xor = Array.from(Array(N), () => Array(N).fill(0));
// Find the prefix_xor
prefix(arr, prefix_xor, n);
// Find submatrix with maximum bitwise xor
Max_xor(prefix_xor, n);
// This code is contributed by rutvik_56.
</script>
Producción:
31
Complejidad del Tiempo: O(n 4 )
Espacio Auxiliar: O(1)
Publicación traducida automáticamente
Artículo escrito por andrew1234 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA