Tutorialspoint.dev

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

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
?>

Output:

3

Time Complexity: O(N2 * M2).
Space Complexity: O(N*M).

Please write comments if you find anything incorrect, or you want to share more information about the topic discussed above.



This article is attributed to GeeksforGeeks.org

leave a comment

code

0 Comments

load comments

Subscribe to Our Newsletter