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”.
Examples:
Input: mat[][] = {{0, 0}, {1, 0}, {1, 1}}, target[][] = {{0, 1}, {1, 0}, {1, 1}}
Output: 1
Explanation: Step 1: Reorder 2nd and 3rd 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 = 1Input: 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 bitsetsbool static cmp(bitset<105>& p1, bitset<105>& p2){ return p1.to_string() < p2.to_string();}// Function to convert the given// matrix into the target matrixint 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 Codeint 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);} |
Java
// Java program for the above approachimport java.util.*;public class Main { // Custom comparator to sort vector // of bitsets static class BitsetComparator implements Comparator<BitSet> { public int compare(BitSet p1, BitSet p2) { return p1.toString().compareTo(p2.toString()); } } // Function to convert the given // matrix into the target matrix static int minCost(List<List<Integer> > a, List<List<Integer> > t) { // Number of rows and columns int n = a.size(); int m = a.get(0).size(); List<BitSet> mat = new ArrayList<>(n); List<BitSet> tar = new ArrayList<>(n); // Iterate over rows for (int i = 0; i < n; i++) { StringBuilder sb = new StringBuilder(); for (int j = 0; j < m; j++) { sb.append(a.get(i).get(j)); } mat.add( i, BitSet.valueOf(new long[] { Long.parseLong(sb.toString(), 2) })); } // Iterate over rows for (int i = 0; i < n; i++) { StringBuilder sb = new StringBuilder(); for (int j = 0; j < m; j++) { sb.append(t.get(i).get(j)); } tar.add( i, BitSet.valueOf(new long[] { Long.parseLong(sb.toString(), 2) })); } // Sort the matrix Collections.sort(tar, new BitsetComparator()); int ans = Integer.MAX_VALUE; // Check all possible rows as the // first row of target for (int i = 0; i < n; i++) { List<BitSet> copy = new ArrayList<>(mat); // Get the flip pattern BitSet flip = (BitSet)copy.get(i).clone(); flip.xor(tar.get(0)); for (int j = 0; j < copy.size(); j++) { copy.get(j).xor(flip); } Collections.sort(copy, new BitsetComparator()); // Number of flip operations // is the count of set bits in flip if (copy.equals(tar)) { ans = Math.min(ans, flip.cardinality()); } } // If it is not possible if (ans == Integer.MAX_VALUE) { return -1; } // Return the answer return ans; } // Driver Code public static void main(String[] args) { // Given matrices List<List<Integer> > matrix = Arrays.asList( Arrays.asList(0, 0), Arrays.asList(1, 0), Arrays.asList(1, 1)); List<List<Integer> > target = Arrays.asList( Arrays.asList(0, 1), Arrays.asList(1, 0), Arrays.asList(1, 1)); // Function Call System.out.println(minCost(matrix, target)); }}// This code is contributed by rutikbhosale |
Python3
# Python code for the above approachimport sys# Function to convert bitset to stringdef bitset_to_str(bs, size): return ''.join(str(bs >> i & 1) for i in range(size - 1, -1, -1))# Custom comparator to sort vector of bitsetsdef cmp(p1, p2): return bitset_to_str(p1, 105) < bitset_to_str(p2, 105)# Function to convert the given matrix into the target matrixdef minCost(a, t): # Number of rows and columns n = len(a) m = len(a[0]) mat = [] tar = [] # Iterate over rows for i in range(n): s = '' for j in range(m): s += str(a[i][j]) mat.append(int(s, 2)) # Iterate over rows for i in range(n): s = '' for j in range(m): s += str(t[i][j]) tar.append(int(s, 2)) # Sort the matrix tar.sort(key=lambda x: bitset_to_str(x, 105)) ans = sys.maxsize # Check all possible rows as the first row of target for i in range(n): copy = mat.copy() # Get the flip pattern flip = copy[i] ^ tar[0] for j in range(len(copy)): copy[j] ^= flip copy.sort(key=lambda x: bitset_to_str(x, 105)) # Number of flip operations is the count of set bits in flip if copy == tar: ans = min(ans, bin(flip).count('1')) # If it is not possible if ans == sys.maxsize: return -1 # Return the answer return ans# Driver Codematrix = [[0, 0], [1, 0], [1, 1]]target = [[0, 1], [1, 0], [1, 1]]print(minCost(matrix, target))# This code is contributed by sdeadityasharma |
Javascript
// JavaScript code for the above approach// Function to convert bitset to stringfunction bitset_to_str(bs, size) { let result = ''; for (let i = size - 1; i >= 0; i--) { result += (bs >> i) & 1; } return result;}// Custom comparator to sort array of bitsetsfunction cmp(p1, p2) { return bitset_to_str(p1, 105) < bitset_to_str(p2, 105) ? -1 : 1;}// Function to convert the given matrix into the target matrixfunction minCost(a, t) { // Number of rows and columns let n = a.length; let m = a[0].length; let mat = []; let tar = []; // Iterate over rows for (let i = 0; i < n; i++) { let s = ''; for (let j = 0; j < m; j++) { s += a[i][j]; } mat.push(parseInt(s, 2)); } // Iterate over rows for (let i = 0; i < n; i++) { let s = ''; for (let j = 0; j < m; j++) { s += t[i][j]; } tar.push(parseInt(s, 2)); } // Sort the matrix tar.sort(cmp); let ans = Number.MAX_SAFE_INTEGER; // Check all possible rows as the first row of target for (let i = 0; i < n; i++) { let copy = [...mat]; // Get the flip pattern let flip = copy[i] ^ tar[0]; for (let j = 0; j < copy.length; j++) { copy[j] ^= flip; } copy.sort(cmp); // Number of flip operations is the count of set bits in flip if (JSON.stringify(copy) === JSON.stringify(tar)) { ans = Math.min(ans, (flip).toString(2).match(/1/g).length); } } // If it is not possible if (ans == Number.MAX_SAFE_INTEGER) { return -1; } // Return the answer return ans;}// Driver Codelet matrix = [ [0, 0], [1, 0], [1, 1]];let target = [ [0, 1], [1, 0], [1, 1]];console.log(minCost(matrix, target));// Contributed by adityasharmadev01 |
C#
// C# code for the above approachusing System;using System.Collections.Generic;using System.Linq;public class Program{ // Function to convert bitset to string public static string BitsetToStr(int bs, int size) { string result = ""; for (int i = size - 1; i >= 0; i--) { result += ((bs >> i) & 1); } return result; } // Custom comparator to sort array of bitsets public static int Cmp(int p1, int p2) { return BitsetToStr(p1, 105).CompareTo(BitsetToStr(p2, 105)); } // Function to convert the given matrix into the target matrix public static int MinCost(int[][] a, int[][] t) { // Number of rows and columns int n = a.Length; int m = a[0].Length; List<int> mat = new List<int>(); List<int> tar = new List<int>(); // Iterate over rows for (int i = 0; i < n; i++) { string s = ""; for (int j = 0; j < m; j++) { s += a[i][j]; } mat.Add(Convert.ToInt32(s, 2)); } // Iterate over rows for (int i = 0; i < n; i++) { string s = ""; for (int j = 0; j < m; j++) { s += t[i][j]; } tar.Add(Convert.ToInt32(s, 2)); } // Sort the matrix tar.Sort(Cmp); int ans = int.MaxValue; // Check all possible rows as the first row of target for (int i = 0; i < n; i++) { List<int> copy = new List<int>(mat); int flip = copy[i] ^ tar[0]; for (int j = 0; j < copy.Count; j++) { copy[j] ^= flip; } copy.Sort(Cmp); // Number of flip operations is the count of set bits in flip if (copy.SequenceEqual(tar)) { ans = Math.Min(ans, Convert.ToString(flip, 2).Count(x => x == '1')); } } // If it is not possible if (ans == int.MaxValue) { return -1; } return ans; } // Driver Code public static void Main() { int[][] matrix = new int[][] { new int[] { 0, 0 }, new int[] { 1, 0 }, new int[] { 1, 1 } }; int[][] target = new int[][] { new int[] { 0, 1 }, new int[] { 1, 0 }, new int[] { 1, 1 } }; Console.WriteLine(MinCost(matrix, target)); }}// This code is contributed by Shivhack999 |
Output:
1
Time Complexity: O(N * M) Auxiliary Space: O(N * M)
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
