Kiểm tra chọn 1 số mỗi hàng ma trận cho XOR > 0 C++

Cho ma trận N×M. Chọn 1 số từ mỗi hàng sao cho XOR của các số chọn > 0.

Ví dụ: 7 7 7 10 10 7 Chọn 7 (hàng 1) và 10 (hàng 2) → 7^10 = 13 > 0.

Giải thuật

1. Tính XOR cột đầu tiên của tất cả hàng. Nếu ≠ 0 → YES
2. Nếu = 0: kiểm tra có hàng nào có ≥2 giá trị khác nhau không. Nếu có → YES (có thể thay đổi lựa chọn)
3. Nếu cả 2 đều không → NO

Ví dụ minh họa

#include <iostream>
#define N 2
#define M 3
using namespace std;

bool isXORnonZero(int matrix[N][M]) {
    int xorVal = 0;
    for (int i = 0; i < N; i++) xorVal ^= matrix[i][0];
    if (xorVal != 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}};
    cout << (isXORnonZero(mat) ? "XOR co gia tri khac 0" : "XOR bang 0");
}

Kết quả

XOR co gia tri khac 0