Score After Flipping Matrix

The idea is to use the properties of binary numbers to implement the solution in a brute force manner.

We know that the maximum number of 1s in a binary number will help in increasing the overall sum if they are as left as possible. One important observation that arises from this fact is that the first bit(extreme left) should be made 1 to maximize the number as 4(100) > 3(011). So, if the first column in any row is 0 then we should toggle that row to obtain 1 in the first column.

Now, for a particular column, we should try maximizing the number of 1s since all 1s will be at the same bit position. Hence, if the number of 1s increases, it will consequently increase the total sum. So, if any column contains more 0s than 1s (or numbers of 1s are less than ‘M / 2’, i.e., half of the number of rows) then we should toggle that column.

We will do this for all columns except column 1, as by doing so, we end up destroying the property mentioned above for column 1.

Algorithm: 

• Declare an integer variable, ‘RESULT’ to store the maximum score of the matrix, ‘MAT’.
• Declare a vector of integers, ‘COUNTOF1SINCOL’, to store the count of the number of 1s in any column.
• Run a loop for i = 0 to M - 1.
  • If MAT[i][0] == 0 that shows that the first column of ‘i’th row contains zero. Therefore,
    • Call the ‘TOGGLE_ROW’ function to toggle all the elements of ‘i’th row.
  • Run a loop for j = 0 to N - 1.
    • If MAT[i][j] == 1 that shows that 1 is present in the ‘j’th column. Therefore.
      • Increment the ‘COUNTOF1SINCOL[j]’ by 1.
• Run a loop for j = 0 to N - 1.
  • If COUNTOF1SINCOL[j] <= M / 2, that shows that number of 0s are more than the number of rows in ‘j’th column. Therefore,
  • Call the ‘TOGGLE_COLUMN’ function to toggle all the elements of the ‘j’th column.
• Run a loop for every row, ‘ROW_ARRAY’ in ‘MAT’.
  • Declare an integer variable, ‘NUM’ that will store the decimal value corresponding to the binary representation of ‘ROW_ARRAY’ .
  • Run a loop for j = N - 1 to j = 0.
    • If ROW_ARRAY[j] == 1 that shows that element at ‘j’th column in the ‘ROW_ARRAY’ is 1. Therefore,
      • Add ‘1 << n - 1 - j’ to ‘NUM’, which is equivalent to adding the decimal place value of the corresponding bit.
• In the end, return ‘RESULT’.

Description of ‘TOGGLE_ROW’ function

This function will take three parameters :

• MAT: A 2 - D Matrix.
• ROW_INDEX: An integer variable representing the Index of the row of which elements has to be toggled.
• N: An integer variable representing the number of columns in the matrix, ‘MAT’.

int TOGGLE_ROW(MAT, ROW_INDEX, N):

• Run a loop for j = 0 to N - 1.
• Store the ‘XOR’ of ‘MAT[ROW_INDEX][j]’ and 1 in ‘MAT[ROW_INDEX][j]’.

Description of ‘TOGGLE_COLUMN’ function

This function will take three parameters :

• MAT: A 2 - D Matrix.
• COLUMN_INDEX: An integer variable representing the Index of the column of which elements has to be toggled.
• M: An integer variable representing the number of rows in the matrix, ‘MAT’.

int TOGGLE_ROW(MAT, COLUMN_INDEX, M):

• Run a loop for i = 0 to M - 1.
• Store the ‘XOR’ of ‘MAT[i][COLUMN_INDEX]’ and 1 in ‘MAT[i][COLUMN_INDEX]’.

O(M * N), where ‘M’ and ‘N’ are the number of rows and columns of the matrix, ‘MAT’, respectively.

The first loop runs ‘M’ times within which the ‘toggleRow’ function takes O(N) time, and another loop also takes O(N) time. This leads to the time complexity of O(M * N).

The second loop runs ‘N’ times within which the ‘toggleColumn’ function takes O(M) time, resulting in O(M * N) time complexity.

The third runs for every row, i.e., ‘M’ times within which another for loop runs ‘N’ times leading to O(M * N) time complexity.

Hence, overall time complexity = O(M * N) + O(M * N) + O(M * N) = O(M * N).

O(1).
 

Since no auxiliary space has been used.