Maximale XOR-waarde in matrix
Gegeven een vierkante matrix (N X N) is het de taak om de maximale XOR-waarde van een volledige rij of een volledige kolom te vinden.
Voorbeelden:
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 eenvoudige oplossing van dit probleem is dat we de matrix twee keer kunnen doorlopen en de maximale xor-waarde rij- en kolomsgewijs kunnen berekenen en uiteindelijk het maximum tussen (xor_row xor_column) kunnen retourneren.
A efficiënte oplossing is dat we de matrix slechts één keer kunnen doorlopen en de maximale XOR-waarde kunnen berekenen.
- Begin met het doorkruisen van de matrix en bereken XOR voor elke indexrij en kolom. We kunnen beide waarden berekenen door indexen op een omgekeerde manier te gebruiken. Dit is mogelijk omdat matrix een vierkante matrix is.
- Bewaar het maximum van beide.
Hieronder vindt u de implementatie:
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>
Uitvoer
maximum XOR value : 12
Tijdcomplexiteit: O(N*N)
ruimtecomplexiteit: O(1)
