Maksimal XOR-værdi i matrix
Givet en kvadratisk matrix (N X N) er opgaven at finde den maksimale XOR-værdi for en komplet række eller en komplet kolonne.
Eksempler:
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 67} {7 8 9 10} {2 4 5 11}} Output : 12 EN enkel løsning af dette problem er, at vi kan krydse matrixen to gange og beregne den maksimale xor-værdi række- og kolonnevis og til sidst returnere maksimum mellem (xor_row xor_column).
EN effektiv løsning er, at vi kun kan krydse matrix én gang og beregne max XOR-værdi.
- Begynd at krydse matrixen og beregne XOR ved hver indeksrække og kolonnevis. Vi kan beregne begge værdier ved at bruge indekser på omvendt måde. Dette er muligt, fordi matrix er en kvadratisk matrix.
- Gem det maksimale af begge.
Nedenfor er implementeringen:
C++ // C++ program to Find maximum XOR value in // matrix either row / column wise #include 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 import java.io.* ; 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 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>
Produktion
maximum XOR value : 12
Tidskompleksitet: O(N*N)
rumkompleksitet : O(1)
