Program to count minimum number of operations to flip columns to make target in Python

Suppose we have a matrix M and a target matrix T with the same number of rows and columns. Now suppose an operation where we flip a particular column in matrix so that all 1s will be converted to 0s and all 0s will be converted to 1s. So if we can reorder the matrix rows for free, find the minimum number of operations required to turn M into T. If there is no solution, then return -1.

So, if the input is like M =

T =

then the output will be 1, as first reorder the rows to−

And then flip column 1 to−

To solve this, we will follow these steps−

• nums1 := a new list, nums2 := a new list

• for each row in matrix, do

  • ths := 0

  • while row is not empty, do

    • ths :=(ths*2) + last element from row, and delete last element of row

  • insert ths at the end of nums1

• for each row in target, do

  • ths := 0

  • while row is non-zero, do

  • ths :=(ths*2) + last element from row, and delete last element of row

  • insert ths at the end of nums2

• ret:= infinity

• for each num in nums1, do

  • cts := a map with distinct elements in nums1 and their frequencies

  • cts[num] := cts[num] - 1

  • my_xor := num XOR nums2[0]

  • for i in range 1 to size of nums2, do

    • needed := my_xor XOR nums2[i]

    • if cts[needed] is zero, then

      • come out from the loop

      • cts[needed] := cts[needed] - 1

    • otherwise,

    • ret:= minimum of ret, and number of set bit of my_xor

    • return ret if ret is not same as infinity otherwise -1

Let us see the following implementation to get better understanding −

Example

 Live Demo

class Solution:    def solve(self, matrix, target):       nums1 = []       nums2 = []       for row in matrix:          ths = 0          while row:             ths = (ths<<1) + row.pop()          nums1.append(ths)       for row in target:          ths = 0          while row:             ths = (ths<<1) + row.pop()          nums2.append(ths)       ret=float('inf')       from collections import Counter       for num in nums1:          cts = Counter(nums1)          cts[num] -= 1          my_xor = num^nums2[0]          for i in range(1,len(nums2)):             needed = my_xor^nums2[i]             if not cts[needed]:                break             cts[needed]-=1          else:             ret=min(ret,bin(my_xor).count('1'))       return ret if ret!=float('inf') else -1 ob = Solution() M = [    [0, 0],    [1, 0],    [1, 1] ] T = [    [0, 1],    [1, 0],    [1, 1] ] print(ob.solve(M,T))

Input

M = [[0, 0],[1, 0],[1, 1]] T = [[0, 1],[1, 0],[1, 1]]

Output

1