Problem statement

https://binarysearch.com/problems/Column-Flips-to-Target/

Solution

Notice that it does not matter in which order we flip and rearrange rows. Imagine that i-th row of matrix B correspones to 0-th row of matrix A. This will uniqueily define all flips we need to make: let us do them and keep counter of tuples of rows and compare if we have the same amount.

Complexity

It is O(m^2n) for time and O(mn) for space.

Code

class Solution:
    def solve(self, A, B):
        B_rows = Counter(tuple(x) for x in B)
        m, n = len(A), len(A[0])
        ans = float("inf")
        for row in B:
            F = [x^y for x, y in zip(A[0], row)]
            cnt = Counter([tuple(x^y for x, y in zip(F, r)) for r in A])
            if cnt == B_rows:
                ans = min(ans, F.count(1))
        
        return ans if ans != float("inf") else -1