ตรวจสอบว่าเลือกตัวเลขจากแต่ละแถวได้ XOR > 0 ใน C++

กำหนด Matrix N×M หาได้ไหมว่าเลือกตัวเลข 1 ตัวจากแต่ละแถว ทำให้ XOR ของตัวเลขที่เลือก > 0

ตัวอย่าง: 7 7 7 10 10 7 → เลือก 7 (Row 1) และ 10 (Row 2) → 7 XOR 10 = 13 > 0 → YES

ข้อสังเกตสำคัญ

1. ถ้า XOR ของคอลัมน์แรกทั้งหมด ≠ 0 → YES (เลือกคอลัมน์แรกทุกแถว)
2. ถ้า XOR = 0 → ตรวจสอบว่ามีแถวไหนที่มีค่าต่างกัน ≥ 2 ค่า หรือไม่
   • มี → สลับเลือกค่าอื่นในแถวนั้น จะทำให้ XOR ≠ 0 → YES
   • ไม่มี (ทุกแถวค่าทุกคอลัมน์เหมือนกัน) → NO

ตัวอย่างโค้ด

#include <iostream>
using namespace std;

#define N 2
#define M 3

bool isXORnonZero(int matrix[N][M]) {
    int xor_val = 0;
    for (int i = 0; i < N; i++)
        xor_val ^= matrix[i][0];

    if (xor_val != 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";
    return 0;
}

ผลลัพธ์

XOR has non-zero value

การพิสูจน์

ให้ X = XOR ของคอลัมน์แรก = 0
หากมีแถว i ที่มี a ≠ b สลับจาก a เป็น b → XOR ใหม่ = X ⊕ a ⊕ b = 0 ⊕ a ⊕ b = a ⊕ b ≠ 0 (เพราะ a ≠ b)

ความซับซ้อน

เวลา: O(N×M), พื้นที่: O(1)