Encuentre una subarray con XOR máximo

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

Deja una respuesta

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *