Maximaler XOR-Wert in der Matrix
Bei einer gegebenen quadratischen Matrix (N X N) besteht die Aufgabe darin, den maximalen XOR-Wert einer vollständigen Zeile oder einer vollständigen Spalte zu ermitteln.
Beispiele:
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 A einfache Lösung Dieses Problem besteht darin, dass wir die Matrix zweimal durchlaufen und den maximalen xor-Wert zeilen- und spaltenweise berechnen und schließlich das Maximum zwischen (xor_row xor_column) zurückgeben können.
A effiziente Lösung ist, dass wir die Matrix nur einmal durchlaufen und den maximalen XOR-Wert berechnen können.
- Beginnen Sie mit dem Durchlaufen der Matrix und berechnen Sie XOR für jede Indexzeile und -spalte. Wir können beide Werte berechnen, indem wir Indizes in umgekehrter Reihenfolge verwenden. Dies ist möglich, weil die Matrix eine quadratische Matrix ist.
- Speichern Sie das Maximum von beidem.
Unten ist die Implementierung:
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>
Ausgabe
maximum XOR value : 12
Zeitkomplexität: O(N*N)
Raumkomplexität: O(1)
