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]’.

The idea is to use the greedy approach.

Suppose a row represents a binary number: 110101. This can be written as 100000 + 010000 + 000000 + 000100 + 000000 + 000001.

So, 110101(53) = 100000(32) + 010000(16) + 000000(0) + 000100(4) + 000000(0) + 000001(1).

It means that a binary number represented by a row can be interpreted as the sum of the decimal place values of 1s in all columns.

So, the total score of the matrix can also be calculated by summing “decimal place value of 1 in a column * the total number of 1s in that column” over all the columns.

As discussed in Approach 1, the first column should have all entries as 1. So, the score obtained from the first column would be ‘(1 << (N - 1)) * M’.

Now, starting from the first column, we will find the number of values that are the same(0 or 1) for each row, with the first column element and store it in the variable, ‘COUNT’.

It is because if they are both 0, then they would be automatically toggled to 1, if we toggle the complete row.

Otherwise, if they are 1,  the row will not be toggled. Hence, effectively, the variable ‘COUNT’ stores the maximum number of 1s in a column.

From Approach 1, it is clear that we have to maximize the number of 1s and thus the ‘count’. Intuitively, if ‘COUNT’ is the number of 1s, then ‘M - COUNT’ is the number of 0s. In Approach 1, we were toggling the column if the number of 0s is more than the number of 1s. So, we can consider that the column will have a ‘max(COUNT, M - COUNT)’ number of 1s. This will result in the score of ‘(1 << (N - 1 - j)) * max(COUNT, M - COUNT)’, where ‘j’ is the column index.

We will sum all these values for all columns (2 to N) and add with the score of 1st column, which would be the final maximum score.
 

Algorithm:

• Declare an integer variable, ‘RESULT’ to store the maximum score of the matrix, ‘MAT’. Assign ‘(1 << (N - 1)) * M’, i.e., the score of the first column in the ‘RESULT’.
• Run a loop for j = 1 to N - 1.
  • Declare an integer variable, ‘COUNT’ and initialize it with 0.
  • Run a loop for i = 0 to M - 1.
    • If MAT[i][0] == MAT[i][j] that shows that the element at column ‘j’ is the same as the element at column ‘0’ in the row ‘i’. Therefore,
      • Increment ‘COUNT’ by 1.
  • Add ‘(1 << (N - 1 - j)) * max(COUNT, M - COUNT)’ to the ‘RESULT’.
• In the end, return ‘RESULT’.