# Minimize cost to convert a given matrix to another by flipping columns and reordering rows

Given two binary matrices **mat[][]** and **target[][]** of dimensions **N * M**, the task is to find the minimum cost to convert the matrix **mat[][]** into **target[][]** using the following operations:

- Flip a particular column in
**mat[][]**such that all**1s**become**0s**and vice-versa. The cost of this operation is**1**. - Reorder the rows of
**mat[][]**. The cost of this operation is 0.

If its not possible to convert the matrix **mat[][]** to **target[][]**, then print **“-1”**.

Attention reader! Don’t stop learning now. Get hold of all the important DSA concepts with the **DSA Self Paced Course** at a student-friendly price and become industry ready. To complete your preparation from learning a language to DS Algo and many more, please refer **Complete Interview Preparation Course****.**

In case you wish to attend **live classes **with experts, please refer **DSA Live Classes for Working Professionals **and **Competitive Programming Live for Students**.

**Examples:**

Input:mat[][] = {{0, 0}, {1, 0}, {1, 1}}, target[][] = {{0, 1}, {1, 0}, {1, 1}}Output:1Explanation:

Step 1: Reorder 2^{nd}and 3^{rd}rows to modify mat[][] to {{0, 0}, {1, 1}, {1, 0}}. Cost = 0

Step 2: Flip the second column . mat[][] modifies to {{0, 1}, {1, 0}, {1, 1}}, which is equal to target[][]. Cost = 1

Input:mat[][] = {{0, 0, 0}, {1, 0, 1}, {1, 1, 0}}, target[][] = {{0, 0, 1}, {1, 0, 1}, {1, 1, 1}}Output:-1

**Approach:** The idea is to convert the rows of the given matrices into bitsets and then find the minimum cost of operation to make the matrices equal. Below are the steps:

- First, convert the rows of
**mat[][]**to binary numbers using bitset. - After completing the above step, find all possible rows which can be the first row of the target matrix.
- The number of flips required to convert the row of
**mat[][]**to**tar[][]**is the count of set bits in the**Bitwise XOR**value of the bitsets. - Compute Bitwise XOR of every row with the flip pattern and check if the new matrix, when sorted, is equal to the sorted
**target[][]**matrix or not. - If they are the same, then store the number of flips.
- Calculate all such count of flips in the above steps and return the minimum among them.

Below is the implementation of the above approach:

## C++

`// C++ program for the above approach` ` ` `#include <bits/stdc++.h>` `using` `namespace` `std;` ` ` `// Custom comparator to sort vector` `// of bitsets` `bool` `static` `cmp(bitset<105>& p1,` ` ` `bitset<105>& p2)` `{` ` ` `return` `p1.to_string() < p2.to_string();` `}` ` ` `// Function to convert the given` `// matrix into the target matrix` `int` `minCost(vector<vector<` `int` `> >& a,` ` ` `vector<vector<` `int` `> >& t)` `{` ` ` ` ` `// Number of rows and columns` ` ` `int` `n = a.size();` ` ` `int` `m = a[0].size();` ` ` ` ` `vector<bitset<105> > mat(n), tar(n);` ` ` ` ` `// Iterate over rows` ` ` `for` `(` `int` `i = 0; i < n; i++) {` ` ` `string s;` ` ` ` ` `for` `(` `int` `j = 0; j < m; j++) {` ` ` `s += ` `char` `(a[i][j] + ` `'0'` `);` ` ` `}` ` ` `mat[i] = bitset<105>(s);` ` ` `}` ` ` ` ` `// Iterate over rows` ` ` `for` `(` `int` `i = 0; i < n; i++) {` ` ` `string s;` ` ` ` ` `for` `(` `int` `j = 0; j < m; j++) {` ` ` `s += ` `char` `(t[i][j] + ` `'0'` `);` ` ` `}` ` ` `tar[i] = bitset<105>(s);` ` ` `}` ` ` ` ` `// Sort the matrix` ` ` `sort(tar.begin(), tar.end(), cmp);` ` ` ` ` `int` `ans = INT_MAX;` ` ` ` ` `// Check all possible rows as the` ` ` `// first row of target` ` ` `for` `(` `int` `i = 0; i < n; i++) {` ` ` ` ` `vector<bitset<105> > copy(mat);` ` ` ` ` `// Get the flip pattern` ` ` `auto` `flip = copy[i] ^ tar[0];` ` ` ` ` `for` `(` `auto` `& row : copy)` ` ` `row ^= flip;` ` ` ` ` `sort(copy.begin(), copy.end(), cmp);` ` ` ` ` `// Number of flip operations` ` ` `// is the count of set bits in flip` ` ` `if` `(copy == tar)` ` ` `ans = min(ans, (` `int` `)flip.count());` ` ` `}` ` ` ` ` `// If it is not possible` ` ` `if` `(ans == INT_MAX)` ` ` `return` `-1;` ` ` ` ` `// Return the answer` ` ` `return` `ans;` `}` ` ` `// Driver Code` `int` `main()` `{` ` ` `// Given matrices` ` ` `vector<vector<` `int` `> > matrix{ { 0, 0 },` ` ` `{ 1, 0 },` ` ` `{ 1, 1 } };` ` ` ` ` `vector<vector<` `int` `> > target{ { 0, 1 },` ` ` `{ 1, 0 },` ` ` `{ 1, 1 } };` ` ` ` ` `// Function Call` ` ` `cout << minCost(matrix, target);` `}` |

**Output:**

1

**Time Complexity:** O(N * M)**Auxiliary Space:** O(N * M)