Minimum operations required to set all elements of binary matrix
Given a binary matrix of N rows and M columns. The operation allowed on the matrix is to choose any index (x, y) and toggle all the elements between the rectangle having top-left as (0, 0) and bottom-right as (x-1, y-1). Toggling the element means changing 1 to 0 and 0 to 1. The task is to find minimum operations required to make set all the elements of the matrix i.e make all elements as 1.
Examples:
Input : mat[][] = 0 0 0 1 1
0 0 0 1 1
0 0 0 1 1
1 1 1 1 1
1 1 1 1 1
Output : 1
In one move, choose (3, 3) to make the
whole matrix consisting of only 1s.
Input : mat[][] = 0 0 1 1 1
0 0 0 1 1
0 0 0 1 1
1 1 1 1 1
1 1 1 1 1
Output : 3
The idea is to start from the end point (N – 1, M – 1) and traverse the matrix in reverse order. Whenever we encounter a cell which has a value of 0, flip it.
Why traversing from end point ?
Suppose there are 0 at (x, y) and (x + 1, y + 1) cell. You shouldn’t flip a cell (x + 1, y + 1) after cell (x, y) because after you flipped (x, y) to 1, in next move to flip (x + 1, y + 1) cell, you will flip again (x, y) to 0. So there is no benefit from the first move for flipping (x, y) cell.
Below is implementation of this approach:
C++
// C++ program to find minimum operations required // to set all the element of binary matrix #include <bits/stdc++.h> #define N 5 #define M 5 using namespace std; // Return minimum operation required to make all 1s. int minOperation( bool arr[N][M]) { int ans = 0; for ( int i = N - 1; i >= 0; i--) { for ( int j = M - 1; j >= 0; j--) { // check if this cell equals 0 if (arr[i][j] == 0) { // increase the number of moves ans++; // flip from this cell to the start point for ( int k = 0; k <= i; k++) { for ( int h = 0; h <= j; h++) { // flip the cell if (arr[k][h] == 1) arr[k][h] = 0; else arr[k][h] = 1; } } } } } return ans; } // Driven Program int main() { bool mat[N][M] = { 0, 0, 1, 1, 1, 0, 0, 0, 1, 1, 0, 0, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1 }; cout << minOperation(mat) << endl; return 0; } |
Java
// Java program to find minimum operations required // to set all the element of binary matrix class GFG { static final int N = 5 ; static final int M = 5 ; // Return minimum operation required to make all 1s. static int minOperation( boolean arr[][]) { int ans = 0 ; for ( int i = N - 1 ; i >= 0 ; i--) { for ( int j = M - 1 ; j >= 0 ; j--) { // check if this cell equals 0 if (arr[i][j] == false ) { // increase the number of moves ans++; // flip from this cell to the start point for ( int k = 0 ; k <= i; k++) { for ( int h = 0 ; h <= j; h++) { // flip the cell if (arr[k][h] == true ) { arr[k][h] = false ; } else { arr[k][h] = true ; } } } } } } return ans; } // Driven Program public static void main(String[] args) { boolean mat[][] = { { false , false , true , true , true }, { false , false , false , true , true }, { false , false , false , true , true }, { true , true , true , true , true }, { true , true , true , true , true } }; System.out.println(minOperation(mat)); } } // This code is contributed // by PrinciRaj1992 |
Python 3
# Python 3 program to find # minimum operations required # to set all the element of # binary matrix # Return minimum operation # required to make all 1s. def minOperation(arr): ans = 0 for i in range (N - 1 , - 1 , - 1 ): for j in range (M - 1 , - 1 , - 1 ): # check if this # cell equals 0 if (arr[i][j] = = 0 ): # increase the # number of moves ans + = 1 # flip from this cell # to the start point for k in range (i + 1 ): for h in range (j + 1 ): # flip the cell if (arr[k][h] = = 1 ): arr[k][h] = 0 else : arr[k][h] = 1 return ans # Driver Code mat = [[ 0 , 0 , 1 , 1 , 1 ], [ 0 , 0 , 0 , 1 , 1 ], [ 0 , 0 , 0 , 1 , 1 ], [ 1 , 1 , 1 , 1 , 1 ], [ 1 , 1 , 1 , 1 , 1 ]] M = 5 N = 5 print (minOperation(mat)) # This code is contributed # by ChitraNayal |
C#
using System; // C# program to find minimum operations required // to set all the element of binary matrix public class GFG { public const int N = 5; public const int M = 5; // Return minimum operation required to make all 1s. public static int minOperation( bool [][] arr) { int ans = 0; for ( int i = N - 1; i >= 0; i--) { for ( int j = M - 1; j >= 0; j--) { // check if this cell equals 0 if (arr[i][j] == false ) { // increase the number of moves ans++; // flip from this cell to the start point for ( int k = 0; k <= i; k++) { for ( int h = 0; h <= j; h++) { // flip the cell if (arr[k][h] == true ) { arr[k][h] = false ; } else { arr[k][h] = true ; } } } } } } return ans; } // Driven Program public static void Main( string [] args) { bool [][] mat = new bool [][] { new bool [] { false , false , true , true , true }, new bool [] { false , false , false , true , true }, new bool [] { false , false , false , true , true }, new bool [] { true , true , true , true , true }, new bool [] { true , true , true , true , true } }; Console.WriteLine(minOperation(mat)); } } // This code is contributed by Shrikant13 |
Javascript
<script> // Javascript program to find minimum operations required // to set all the element of binary matrix let N = 5; let M = 5; // Return minimum operation required to make all 1s. function minOperation(arr) { let ans = 0; for (let i = N - 1; i >= 0; i--) { for (let j = M - 1; j >= 0; j--) { // check if this cell equals 0 if (arr[i][j] == false ) { // increase the number of moves ans++; // flip from this cell to the start point for (let k = 0; k <= i; k++) { for (let h = 0; h <= j; h++) { // flip the cell if (arr[k][h] == true ) { arr[k][h] = false ; } else { arr[k][h] = true ; } } } } } } return ans; } // Driven Program let mat = [[ 0, 0, 1, 1, 1], [0, 0, 0, 1, 1], [0, 0, 0, 1, 1], [1, 1, 1, 1, 1], [1, 1, 1, 1, 1]] document.write(minOperation(mat)) // This code is contributed by avanitrachhadiya2155 </script> |
PHP
<?php // PHP program to find minimum // operations required to set // all the element of binary matrix $N = 5; $M = 5; // Return minimum operation // required to make all 1s. function minOperation(& $arr ) { global $N , $M ; $ans = 0; for ( $i = $N - 1; $i >= 0; $i --) { for ( $j = $M - 1; $j >= 0; $j --) { // check if this // cell equals 0 if ( $arr [ $i ][ $j ] == 0) { // increase the // number of moves $ans ++; // flip from this cell // to the start point for ( $k = 0; $k <= $i ; $k ++) { for ( $h = 0; $h <= $j ; $h ++) { // flip the cell if ( $arr [ $k ][ $h ] == 1) $arr [ $k ][ $h ] = 0; else $arr [ $k ][ $h ] = 1; } } } } } return $ans ; } // Driver Code $mat = array ( array (0, 0, 1, 1, 1), array (0, 0, 0, 1, 1), array (0, 0, 0, 1, 1), array (1, 1, 1, 1, 1), array (1, 1, 1, 1, 1)); echo minOperation( $mat ); // This code is contributed // by ChitraNayal ?> |
3
Time Complexity: O(N2 * M2).
Auxiliary Space: O(N*M).
Approach 2:
In this implementation, iterate column-wise from right to left. For each column, count the number of ones and zeros in that column. Then, take the minimum of ones and zeros and add it to the flips count. This represents the minimum number of flips required for that column.
Finally, return the total flips count, which represents the minimum operations required to set all the elements of the binary matrix.
Please note that this implementation assumes that the input matrix is a vector of vectors (vector<vector<int>>). If you have a different representation, you may need to modify the code accordingly.
C++
#include <iostream> #include <vector> using namespace std; int minOperation(vector<vector< int >>& matrix) { int rows = matrix.size(); int cols = matrix[0].size(); int flips = 0; for ( int c = cols - 1; c >= 0; c--) { int ones = 0; for ( int r = 0; r < rows; r++) { if (matrix[r] == 1) ones++; } int zeros = rows - ones; flips += min(ones, zeros); } return flips; } int main() { vector<vector< int >> matrix = { {0, 0, 1, 1, 1}, {0, 0, 0, 1, 1}, {0, 0, 0, 1, 1}, {1, 1, 1, 1, 1}, {1, 1, 1, 1, 1} }; cout << minOperation(matrix) << endl; return 0; } |
Java
// Java code for above approach import java.util.*; class Main { static int minOperation(List<List<Integer>> matrix) { int rows = matrix.size(); int cols = matrix.get( 0 ).size(); int flips = 0 ; for ( int c = cols - 1 ; c >= 0 ; c--) { int ones = 0 ; for ( int r = 0 ; r < rows; r++) { if (matrix.get(r).get(c) == 1 ) ones++; } int zeros = rows - ones; flips += Math.min(ones, zeros); } return flips; } public static void main(String[] args) { List<List<Integer>> matrix = new ArrayList<>(); matrix.add(Arrays.asList( 0 , 0 , 1 , 1 , 1 )); matrix.add(Arrays.asList( 0 , 0 , 0 , 1 , 1 )); matrix.add(Arrays.asList( 0 , 0 , 0 , 1 , 1 )); matrix.add(Arrays.asList( 1 , 1 , 1 , 1 , 1 )); matrix.add(Arrays.asList( 1 , 1 , 1 , 1 , 1 )); System.out.println(minOperation(matrix)); } } // This code is contributed by Utkarsh Kumar |
Python3
def min_operation(matrix): # Get the number of rows and columns in the matrix rows = len (matrix) cols = len (matrix[ 0 ]) # Initialize the variable to store the total flips required flips = 0 # Iterate over each column in reverse order (from right to left) for c in range (cols - 1 , - 1 , - 1 ): # Count the number of ones in the current column ones = 0 for r in range (rows): if matrix[r] = = 1 : ones + = 1 # Calculate the number of zeros in the current column zeros = rows - ones # Add the minimum of ones and zeros to the total flips required flips + = min (ones, zeros) # Return the total flips required to make all columns have an equal number of ones and zeros return flips if __name__ = = "__main__" : # Given input matrix matrix = [ [ 0 , 0 , 1 , 1 , 1 ], [ 0 , 0 , 0 , 1 , 1 ], [ 0 , 0 , 0 , 1 , 1 ], [ 1 , 1 , 1 , 1 , 1 ], [ 1 , 1 , 1 , 1 , 1 ] ] # Call the min_operation function with the given matrix and print the result print (min_operation(matrix)) # This code is contributed by akshitaguprzj3 |
C#
using System; using System.Collections.Generic; class Program { // Function to calculate the minimum number of flips // required to make columns balanced static int MinOperation(List<List< int > > matrix) { int rows = matrix.Count; int cols = matrix[0].Count; int flips = 0; for ( int c = cols - 1; c >= 0; c--) { int ones = 0; for ( int r = 0; r < rows; r++) { if (matrix[r] == 1) ones++; } int zeros = rows - ones; flips += Math.Min(ones, zeros); } return flips; } static void Main( string [] args) { // Define the input matrix List<List< int > > matrix = new List<List< int > >{ new List< int >{ 0, 0, 1, 1, 1 }, new List< int >{ 0, 0, 0, 1, 1 }, new List< int >{ 0, 0, 0, 1, 1 }, new List< int >{ 1, 1, 1, 1, 1 }, new List< int >{ 1, 1, 1, 1, 1 } }; // Calculate and display the minimum number of flips // required Console.WriteLine(MinOperation(matrix)); } } |
Javascript
function minOperation(matrix) { // Get the number of rows and columns in the matrix const rows = matrix.length; const cols = matrix[0].length; // Initialize a variable to count the flips let flips = 0; // Iterate through the columns in reverse order for (let c = cols - 1; c >= 0; c--) { let ones = 0; // Count the number of ones in the current column for (let r = 0; r < rows; r++) { if (matrix[r] === 1) { ones++; } } // Calculate the number of zeros in the current column const zeros = rows - ones; // Add the minimum of ones and zeros to the flips count flips += Math.min(ones, zeros); } return flips; } // Define the matrix as a 2D array const matrix = [ [0, 0, 1, 1, 1], [0, 0, 0, 1, 1], [0, 0, 0, 1, 1], [1, 1, 1, 1, 1], [1, 1, 1, 1, 1] ]; // Call the minOperation function and print the result console.log(minOperation(matrix)); |
6
Time Complexity: O(N * M).
Auxiliary Space: O(1).
Contact Us