logo

الحد الأقصى لقيمة XOR في المصفوفة

بالنظر إلى مصفوفة مربعة (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 القصوى. 



  1. ابدأ باجتياز المصفوفة وحساب XOR في كل صف وعمود من الفهرس. يمكننا حساب كلتا القيمتين باستخدام الفهارس بطريقة عكسية. وهذا ممكن لأن المصفوفة هي مصفوفة مربعة.
  2. قم بتخزين الحد الأقصى لكليهما.

وفيما يلي التنفيذ: 

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> 

الإخراج
maximum XOR value : 12

التعقيد الزمني : O(N*N) 
تعقيد الفضاء : O(1)