Chương trình tìm số cột lật để có tối đa hàng giống nhau trong Python

Cho ma trận nhị phân. Có thể chọn bất kỳ cột nào và lật tất cả giá trị trong cột đó (0→1, 1→0). Mục tiêu: tìm số hàng tối đa mà sau khi lật các cột, tất cả giá trị trong hàng đó bằng nhau (toàn 0 hoặc toàn 1).

Ví dụ

Ma trận:

[[0, 0, 0],
 [0, 0, 1],
 [1, 1, 0]]

Lật 2 cột đầu → ma trận thành:
[[1, 1, 0],
 [1, 1, 1],
 [0, 0, 0]]
Hai hàng cuối toàn giá trị giống nhau → kết quả: 2.

Quan sát quan trọng
Hai hàng sẽ trở nên giống nhau sau lật cột nếu chúng giống nhau hoặc nghịch đảo nhau (mỗi cột khác nhau). Do đó, ta nhóm các hàng theo mẫu hoặc mẫu nghịch đảo.

Thuật toán

  
Với mỗi hàng row, tạo hàng nghịch đảo inv_row (XOR 1).
  
Đếm số hàng trong ma trận trùng với row hoặc inv_row.
  
Cập nhật kết quả tối đa.


Triển khai Python
class Solution:
    def solve(self, matrix):
        rows = matrix
        max_count = 0
        for row in rows:
            inv_row = [1 - x for x in row]  # hoặc [x ^ 1 for x in row]
            count = 0
            for other in rows:
                if other == row or other == inv_row:
                    count += 1
            max_count = max(max_count, count)
        return max_count

# Test
ob = Solution()
matrix = [[0,0,0], [0,0,1], [1,1,0]]
print(ob.solve(matrix))  # Output: 2

Độ phức tạp

  
Thời gian: O(m² × n) với m hàng, n cột.
  
Không gian: O(n) cho hàng nghịch đảo tạm.

Có thể tối ưu về O(m × n) bằng cách dùng tuple làm key trong dictionary đếm tần suất.