주어진 정사각 행렬(N X N)의 작업은 전체 행 또는 전체 열의 최대 XOR 값을 찾는 것입니다.
예:
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 에이 간단한 해결책 이 문제는 행렬을 두 번 탐색하여 행 방향 및 열 방향으로 최대 xor 값을 계산하고 마지막으로 (xor_row xor_column) 사이의 최대값을 반환할 수 있다는 것입니다.
에이 효율적인 솔루션 행렬을 한 번만 순회하여 최대 XOR 값을 계산할 수 있다는 것입니다.
- 행렬 탐색을 시작하고 각 인덱스 행과 열 단위로 XOR을 계산합니다. 인덱스를 역방향으로 사용하여 두 값을 모두 계산할 수 있습니다. 이는 행렬이 정사각 행렬이기 때문에 가능합니다.
- 둘 다의 최대값을 저장합니다.
다음은 구현입니다.
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>
산출
maximum XOR value : 12
시간복잡도 : O(N*N)
공간 복잡도 : O(1)