## Google Interview Question

SDE1s**Country:**United States

If x+y-1 is odd you can make any pattern with row/column flips.

Else

If the exor of all cells is 0 then this is a valid pattern

However if it is 1 then you cannot make that pattern

Label all cells in the grid with capital letters

ABC

DEF

Let the lower case letter be true if it was the center of a flip

a= true

111

100

Write the equation for each cell

A = a exor b exor c exor d

B = a exor b exor c exor e

C…

Exor all capital letters

Simplify

z exor z -> 0

0 exor z -> z

…

When you flip a row / column you change x+y-1 cells

If(x+y-1) is even then the exor of all bits will = 0

If(x+y-1) is odd then exor of A….. = exor a…. so that does not matter

If someone can write a better explanation please do. It took me a long time to figure this out and I want to move on. It seems like a induction proof would be good for this.

E.g.

0, 1, 1,

0, 1, 1,

0, 0, 0,

--- Flip(0, 1)

1, 0, 0,

0, 0, 1,

0, 1, 0,

--- Flip(1, 1)

1, 1, 0,

1, 1, 0,

0, 0, 0,

--- Flip(2, 1)

1, 0, 0,

1, 0, 0,

1, 1, 1,

--- Flip(2, 0)

0, 0, 0,

0, 0, 0,

0, 0, 0,

Brute force:

- Alex December 04, 2017