Maximalt XOR-värde i matris
Givet en kvadratisk matris (N X N) är uppgiften att hitta det maximala XOR-värdet för en hel rad eller en hel kolumn.
Exempel:
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 enkel lösning av detta problem är att vi kan gå igenom matrisen två gånger och beräkna maximalt xor-värde radvis och kolumnvis och till sist returnera det maximala mellan (xor_row xor_column).
A effektiv lösning är att vi bara kan gå igenom matrisen en gång och beräkna max XOR-värde.
- Börja gå igenom matrisen och beräkna XOR vid varje indexrad och kolumnvis. Vi kan beräkna båda värdena genom att använda index på omvänt sätt. Detta är möjligt eftersom matris är en kvadratisk matris.
- Lagra maximalt av båda.
Nedan är 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
Tidskomplexitet: O(N*N)
rymdkomplexitet: O(1)
