FastPrep
Problem · Matrix

Min Flips to Make Grid Palindrome

Learn this problem
● HardGooglePHONE SCREEN
See Google hiring insights

Problem statement

You're working on a data storage system that represents information in a binary grid. For error correction and symmetry, every row and column must be a palindrome.

Additionally, due to hardware constraints, the total number of 1s must be divisible by 4.

You may flip any bit, changing 0 to 1 or 1 to 0. Return the minimum number of flips needed to make the grid valid.

Function

minFlips(grid: int[][]) → int

Examples

Example 1

grid = [[1, 0, 1], [0, 1, 0], [1, 0, 0]]return = 2
Flip the bottom-right 0 to 1 and the center 1 to 0. The resulting grid is [[1, 0, 1], [0, 0, 0], [1, 0, 1]], whose rows and columns are palindromes and whose four 1s are divisible by 4. One flip cannot satisfy both requirements, so the minimum is 2.

Constraints

  • grid is a non-empty rectangular matrix.
  • Every value in grid is either 0 or 1.

More Google problems

drafts saved locally
public int minFlips(int[][] grid) {
  // write your code here
}
grid[[1, 0, 1], [0, 1, 0], [1, 0, 0]]
expected2
checking account