Given a Binary matrix of size MxN, the task is to maximize the score of Matrix by making any number of moves (including zero moves), such that,
- every row is interpreted as a Binary Number, and
- the score of the matrix is the sum of these binary numbers.
- A move is defined as choosing any row or column and toggling/flipping each value in that row or column (i.e., toggling all 0’s to 1’s, and visa-versa).
Examples:
Input: grid = [[0,1,1,1],
[1,0,0,0],
[1,1,0,0]]Output: 41
Explanation: After making moves as shown in the image below, the final score will be 1111 + 1111 + 1011 = 15 + 15 + 11 = 41.
Input: grid = [[0]]
Output: 1
Explanation: 0b1 = 1.
Approach: We can solve this problem optimally using the idea that
To make value large its MSB should always be ‘1’. So we will make grid[i][0] = 1 for every row [ i=0…n-1].
- Now we will traverse from left to right and check for every column for the count of 1’s and 0’s and if any point we have no. of 0’s greater than 1’s we will toggle that column to make 1’s >= 0’s .
- In the end, we will calculate the final score.
Below is the implementation of the above approach :
C++
// C++ implimentation of above idea#include <bits/stdc++.h>using namespace std;// function to toggle the whole columnvoid flipCol(int col, vector<vector<int> >& grid){ for (int j = 0; j < grid.size(); j++) { grid[j][col] ^= 1; }}// function to toggle the whole rowvoid flipRow(int row, vector<vector<int> >& grid){ for (int i = 0; i < grid[0].size(); i++) { grid[row][i] ^= 1; }}int matrixScore(vector<vector<int> >& grid){ int n = grid.size(); int m = grid[0].size(); // MSB should be 1 of 0th column // to get the maximum value for (int i = 0; i < n; i++) { if (grid[i][0] == 0) { flipRow(i, grid); } } // cheacking which column has more 0's than 1's // and toggling them. for (int j = 0; j < m; j++) { int zeros = 0; for (int i = 0; i < n; i++) { if (grid[i][j] == 0) zeros++; } if (zeros > (n - zeros)) { flipCol(j, grid); } } // Calculate the answer int sum = 0; for (int i = 0; i < n; i++) { for (int j = 0; j < m; j++) { if (grid[i][j]) { sum += (1LL << (m - j - 1)); } } } return sum;}// Driver Codeint main(){ int n, m; n = 3; m = 4; vector<vector<int> > grid = { { 0, 1, 1, 1 }, { 1, 0, 0, 0 }, { 1, 1, 0, 0 } }; for (int i = 0; i < n; i++) { for (int j = 0; j < m; j++) { cin >> grid[i][j]; } } cout << "Maximum Value : " << matrixScore(grid) << endl;} |
Java
// Java Code of above approach:import java.util.*;public class GFG { // function to toggle the whole column private static void flipCol(int col, int[][] grid) { for (int j = 0; j < grid.length; j++) { grid[j][col] ^= 1; } } // function to toggle the whole row private static void flipRow(int row, int[][] grid) { for (int i = 0; i < grid[0].length; i++) { grid[row][i] ^= 1; } } public static int matrixScore(int[][] grid) { int n = grid.length; int m = grid[0].length; // MSB should be 1 of 0th column // to get the maximum value for (int i = 0; i < n; i++) { if (grid[i][0] == 0) { flipRow(i, grid); } } // checking which column has more 0's than 1's // and toggling them. for (int j = 0; j < m; j++) { int zeros = 0; for (int i = 0; i < n; i++) { if (grid[i][j] == 0) zeros++; } if (zeros > (n - zeros)) { flipCol(j, grid); } } // Calculate the answer int sum = 0; for (int i = 0; i < n; i++) { for (int j = 0; j < m; j++) { if (grid[i][j] == 1) { sum += (1 << (m - j - 1)); } } } return sum; } // Driver Code public static void main(String[] args) { int n = 3; int m = 4; int[][] grid = { { 0, 1, 1, 1 }, { 1, 0, 0, 0 }, { 1, 1, 0, 0 } }; System.out.println("Maximum Value : " + matrixScore(grid)); }}// this code is contributed by uttamdp_10 |
Python3
# python implementation of above approach:def flipCol(col, grid): for j in range(len(grid)): grid[j][col] ^= 1def flipRow(row, grid): for i in range(len(grid[0])): grid[row][i] ^= 1def matrixScore(grid): n = len(grid) m = len(grid[0]) # MSB should be 1 of 0th column # to get the maximum value for i in range(n): if grid[i][0] == 0: flipRow(i, grid) # Checking which column has more 0's than 1's # and toggling them. for j in range(m): zeros = sum(1 for i in range(n) if grid[i][j] == 0) if zeros > n - zeros: flipCol(j, grid) # Calculate the answer total_sum = 0 for i in range(n): for j in range(m): if grid[i][j] == 1: total_sum += (1 << (m - j - 1)) return total_sum# Driver Codeif __name__ == "__main__": n, m = 3, 4 grid = [[0, 1, 1, 1], [1, 0, 0, 0], [1, 1, 0, 0]] print("Maximum Value:", matrixScore(grid))# this code is contributed by uttamdp_10 |
C#
// C# implimentation of above ideausing System;using System.Collections.Generic;class Program{ // function to toggle the whole column static void FlipCol(int col, List<List<int>> grid) { for (int j = 0; j < grid.Count; j++) { grid[j][col] ^= 1; } } // function to toggle the whole row static void FlipRow(int row, List<List<int>> grid) { for (int i = 0; i < grid[0].Count; i++) { grid[row][i] ^= 1; } } static int MatrixScore(List<List<int>> grid) { int n = grid.Count; int m = grid[0].Count; // MSB should be 1 of 0th column // to get the maximum value for (int i = 0; i < n; i++) { if (grid[i][0] == 0) { FlipRow(i, grid); } } // checking which column has more 0's than 1's // and toggling them. for (int j = 0; j < m; j++) { int zeros = 0; for (int i = 0; i < n; i++) { if (grid[i][j] == 0) zeros++; } if (zeros > (n - zeros)) { FlipCol(j, grid); } } // Calculate the answer int sum = 0; for (int i = 0; i < n; i++) { for (int j = 0; j < m; j++) { if (grid[i][j] != 0) { sum += (1 << (m - j - 1)); } } } return sum; } // Driver Code static void Main(string[] args) { int n = 3; int m = 4; List<List<int>> grid = new List<List<int>> { new List<int> { 0, 1, 1, 1 }, new List<int> { 1, 0, 0, 0 }, new List<int> { 1, 1, 0, 0 } }; // Input grid if needed /*for (int i = 0; i < n; i++) { string[] input = Console.ReadLine().Split(); grid.Add(new List<int>()); for (int j = 0; j < m; j++) { grid[i].Add(int.Parse(input[j])); } }*/ Console.WriteLine("Maximum Value : " + MatrixScore(grid)); }} |
Javascript
function flipCol(col, grid) { for (let j = 0; j < grid.length; j++) { grid[j][col] ^= 1; }}// Function to toggle the whole rowfunction flipRow(row, grid) { for (let i = 0; i < grid[0].length; i++) { grid[row][i] ^= 1; }}function matrixScore(grid) { const n = grid.length; const m = grid[0].length; // MSB should be 1 of 0th column to // get the maximum value for (let i = 0; i < n; i++) { if (grid[i][0] === 0) { flipRow(i, grid); } } // Checking which column has more // 0's than 1's and toggling them for (let j = 0; j < m; j++) { let zeros = 0; for (let i = 0; i < n; i++) { if (grid[i][j] === 0) zeros++; } if (zeros > (n - zeros)) { flipCol(j, grid); } } // Calculate the answer let sum = 0; for (let i = 0; i < n; i++) { for (let j = 0; j < m; j++) { if (grid[i][j]) { sum += 1 << (m - j - 1); } } } return sum;}// Driver codeconst n = 3;const m = 4;const grid = [ [0, 1, 1, 1], [1, 0, 0, 0], [1, 1, 0, 0]];console.log("Maximum Value:", matrixScore(grid)); |
Output
Maximum Value : 41
Time Complexity: O(N*M)
Auxiliary Space Complexity: O(1)
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!