Dada una array cuadrada (NXN), la tarea es encontrar el valor XOR máximo de una fila completa o una columna completa.
Ejemplos:
Input : N = 3
mat[3][3] = {{1, 0, 4},
{3, 7, 2},
{5, 9, 10} };
Output : 14
We get this maximum XOR value by doing XOR
of elements in second column 0 ^ 7 ^ 9 = 14
Input : N = 4
mat[4][4] = { {1, 2, 3, 6},
{4, 5, 6,7},
{7, 8, 9, 10},
{2, 4, 5, 11}}
Output : 12
Una solución simple de este problema es que podemos atravesar la array dos veces y calcular el valor máximo de xor en filas y columnas, y finalmente devolver el máximo entre (xor_fila, xor_columna).
Una solución eficiente es que podemos atravesar la array solo una vez y calcular el valor máximo de XOR.
- Comience a recorrer la array y calcule XOR en cada fila y columna del índice. Podemos calcular ambos valores usando índices de manera inversa. Esto es posible porque matrix es una array cuadrada.
- Almacena el máximo de ambos.
A continuación se muestra la implementación:
C++
// C++ program to Find maximum XOR value in
// matrix either row / column wise
#include<iostream>
using namespace std;
// maximum number of row and column
const int MAX = 1000;
// function return the maximum xor value that is
// either row or column wise
int maxXOR(int mat[][MAX], int N)
{
// for row xor and column xor
int r_xor, c_xor;
int max_xor = 0;
// traverse matrix
for (int i = 0 ; i < N ; i++)
{
r_xor = 0, c_xor = 0;
for (int j = 0 ; j < N ; j++)
{
// xor row element
r_xor = r_xor^mat[i][j];
// for each column : j is act as row & i
// act as column xor column element
c_xor = c_xor^mat[j][i];
}
// update maximum between r_xor , c_xor
if (max_xor < max(r_xor, c_xor))
max_xor = max(r_xor, c_xor);
}
// return maximum xor value
return max_xor;
}
// driver Code
int main()
{
int N = 3;
int mat[][MAX] = {{1 , 5, 4},
{3 , 7, 2 },
{5 , 9, 10}
};
cout << "maximum XOR value : "
<< maxXOR(mat, N);
return 0;
}
Java
// Java program to Find maximum XOR value in
// matrix either row / column wise
class GFG {
// maximum number of row and column
static final int MAX = 1000;
// function return the maximum xor value
// that is either row or column wise
static int maxXOR(int mat[][], int N)
{
// for row xor and column xor
int r_xor, c_xor;
int max_xor = 0;
// traverse matrix
for (int i = 0 ; i < N ; i++)
{
r_xor = 0; c_xor = 0;
for (int j = 0 ; j < N ; j++)
{
// xor row element
r_xor = r_xor^mat[i][j];
// for each column : j is act as row & i
// act as column xor column element
c_xor = c_xor^mat[j][i];
}
// update maximum between r_xor , c_xor
if (max_xor < Math.max(r_xor, c_xor))
max_xor = Math.max(r_xor, c_xor);
}
// return maximum xor value
return max_xor;
}
//driver code
public static void main (String[] args)
{
int N = 3;
int mat[][] = { {1, 5, 4},
{3, 7, 2},
{5, 9, 10}};
System.out.print("maximum XOR value : "
+ maxXOR(mat, N));
}
}
// This code is contributed by Anant Agarwal.
Python3
# Python3 program to Find maximum
# XOR value in matrix either row / column wise
# maximum number of row and column
MAX = 1000
# Function return the maximum
# xor value that is either row
# or column wise
def maxXOR(mat, N):
# For row xor and column xor
max_xor = 0
# Traverse matrix
for i in range(N):
r_xor = 0
c_xor = 0
for j in range(N):
# xor row element
r_xor = r_xor ^ mat[i][j]
# for each column : j is act as row & i
# act as column xor column element
c_xor = c_xor ^ mat[j][i]
# update maximum between r_xor , c_xor
if (max_xor < max(r_xor, c_xor)):
max_xor = max(r_xor, c_xor)
# return maximum xor value
return max_xor
# Driver Code
N = 3
mat= [[1 , 5, 4],
[3 , 7, 2 ],
[5 , 9, 10]]
print("maximum XOR value : ",
maxXOR(mat, N))
# This code is contributed by Anant Agarwal.
C#
// C# program to Find maximum XOR value in
// matrix either row / column wise
using System;
class GFG
{
// maximum number of row and column
// function return the maximum xor value
// that is either row or column wise
static int maxXOR(int [,]mat, int N)
{
// for row xor and column xor
int r_xor, c_xor;
int max_xor = 0;
// traverse matrix
for (int i = 0 ; i < N ; i++)
{
r_xor = 0; c_xor = 0;
for (int j = 0 ; j < N ; j++)
{
// xor row element
r_xor = r_xor^mat[i, j];
// for each column : j is act as row & i
// act as column xor column element
c_xor = c_xor^mat[j, i];
}
// update maximum between r_xor , c_xor
if (max_xor < Math.Max(r_xor, c_xor))
max_xor = Math.Max(r_xor, c_xor);
}
// return maximum xor value
return max_xor;
}
// Driver code
public static void Main ()
{
int N = 3;
int [,]mat = { {1, 5, 4},
{3, 7, 2},
{5, 9, 10}};
Console.Write("maximum XOR value : "
+ maxXOR(mat, N));
}
}
// This code is contributed by nitin mittal.
PHP
<?php
// PHP program to Find
// maximum XOR value in
// matrix either row or
// column wise
// maximum number of
// row and column
$MAX = 1000;
// function return the maximum
// xor value that is either
// row or column wise
function maxXOR($mat, $N)
{
// for row xor and
// column xor
$r_xor; $c_xor;
$max_xor = 0;
// traverse matrix
for ($i = 0 ; $i < $N ; $i++)
{
$r_xor = 0; $c_xor = 0;
for ($j = 0 ; $j < $N ; $j++)
{
// xor row element
$r_xor = $r_xor^$mat[$i][$j];
// for each column : j
// is act as row & i
// act as column xor
// column element
$c_xor = $c_xor^$mat[$j][$i];
}
// update maximum between
// r_xor , c_xor
if ($max_xor < max($r_xor, $c_xor))
$max_xor = max($r_xor, $c_xor);
}
// return maximum
// xor value
return $max_xor;
}
// Driver Code
$N = 3;
$mat = array(array(1, 5, 4),
array(3, 7, 2),
array(5, 9, 10));
echo "maximum XOR value : "
, maxXOR($mat, $N);
// This code is contributed by anuj_67.
?>
Javascript
<script>
// Javascript program to Find
// maximum XOR value in
// matrix either row / column wise
// maximum number of row and column
const MAX = 1000;
// function return the maximum
// xor value that is
// either row or column wise
function maxXOR(mat, N)
{
// for row xor and column xor
let r_xor, c_xor;
let max_xor = 0;
// traverse matrix
for (let i = 0 ; i < N ; i++)
{
r_xor = 0, c_xor = 0;
for (let j = 0 ; j < N ; j++)
{
// xor row element
r_xor = r_xor^mat[i][j];
// for each column : j
// is act as row & i
// act as column xor
// column element
c_xor = c_xor^mat[j][i];
}
// update maximum between r_xor , c_xor
if (max_xor < Math.max(r_xor, c_xor))
max_xor = Math.max(r_xor, c_xor);
}
// return maximum xor value
return max_xor;
}
// driver Code
let N = 3;
let mat = [[1 , 5, 4],
[3 , 7, 2 ],
[5 , 9, 10]];
document.write("maximum XOR value : "
+ maxXOR(mat, N));
</script>
Producción
maximum XOR value : 12
Complejidad temporal: O(N*N)
Complejidad espacial: O(1)
Este artículo es una contribución de Nishant_Singh (Pintu) . Si te gusta GeeksforGeeks y te gustaría contribuir, también puedes escribir un artículo usando write.geeksforgeeks.org o enviar tu artículo por correo a review-team@geeksforgeeks.org. Vea su artículo que aparece en la página principal de GeeksforGeeks y ayude a otros Geeks.
Publicación traducida automáticamente
Artículo escrito por GeeksforGeeks-1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA