Kun on annettu neliömatriisi (N X N), tehtävänä on löytää kokonaisen rivin tai kokonaisen sarakkeen suurin XOR-arvo.
Esimerkkejä:
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 yksinkertainen ratkaisu Tämä ongelma on se, että voimme kulkea matriisin kahdesti ja laskea maksimi xor-arvon riveittäin & sarakkeittain ja lopulta palauttaa maksimin välillä (xor_row xor_column).
A tehokas ratkaisu voimme kulkea matriisin läpi vain kerran ja laskea max XOR -arvon.
- Aloita matriisin läpikulku ja laske XOR jokaiselta indeksiriviltä ja sarakkeelta. Voimme laskea molemmat arvot käyttämällä indeksejä käänteisellä tavalla. Tämä on mahdollista, koska matriisi on neliömatriisi.
- Säilytä mahdollisimman paljon molempia.
Alla toteutus:
C++// C++ program to Find maximum XOR value in // matrix either row / column wise #include
// 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 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# 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 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. ?> <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>
Lähtö
maximum XOR value : 12
Aika monimutkaisuus: O(N*N)
avaruuden monimutkaisuus: O(1)