ตรวจสอบว่าสามารถเลือกตัวเลขจากทุกแถวได้หรือไม่ xor ของตัวเลขมากกว่าศูนย์ใน C++

สมมติว่าเรามีอาร์เรย์ 2 มิติขนาด N x M หนึ่งรายการ ภารกิจคือตรวจสอบว่าเราเลือกตัวเลขจากทุกแถวได้หรือไม่ ในลักษณะที่ XOR ขององค์ประกอบเหล่านั้นไม่เป็นศูนย์หรือมากกว่า 0 สมมติว่าเมทริกซ์หนึ่งตัวคือ แบบนี้ −

ถ้าเราดำเนินการ XOR คำตอบจะไม่เป็นศูนย์ เนื่องจากองค์ประกอบสุดท้ายยกเว้นของสองแถวคือ 7 และ 10

การแก้ปัญหานี้จะง่ายมาก เริ่มแรกตรวจสอบว่า XOR ขององค์ประกอบของคอลัมน์แรกของแต่ละแถวเป็น 0 หรือไม่ ถ้าไม่ใช่ศูนย์ก็เป็นไปได้ มิฉะนั้น ให้ตรวจสอบว่าแถวใดมีองค์ประกอบที่แตกต่างกันตั้งแต่สององค์ประกอบขึ้นไปหรือไม่ ถ้าใช่ ก็เป็นไปได้เช่นกัน หากทั้งสองเงื่อนไขข้างต้นไม่เป็นไปตามเงื่อนไขข้างต้น ก็ไม่สามารถทำได้

ตัวอย่าง

#include<iostream>
using namespace std;
#define N 2
#define M 3
bool isXORnonZero(int matrix[N][M]) {
   int xor_value = 0;
   for (int i = 0; i < N; i++) {
      xor_value ^= matrix[i][0];
   }
   if (xor_value != 0)
      return true;
   for (int i = 0; i < N; i++) {
      for (int j = 1; j < M; j++) {
         if (matrix[i][j] != matrix[i][0])
         return true;
      }
   }
   return false;
}
int main() {
   int mat[N][M] = {
      { 7, 7, 7 },
      { 10, 10, 7 }
   };
   if (isXORnonZero(mat))
      cout << "XOR has non-zero value";
   else
      cout << "XOR has zero value";
}

ผลลัพธ์

XOR has non-zero value