Google | Virtual Onsite | flipping coins problem
Anonymous User
3534

you are ginve a matrix of 0/1

00100
00100
00100
11011
00100

you can flip any row/column, flip means change all 0->1,1->0
return if its possible to change the matrix to all 0s

in above , we can fllip middle column and matrix will become
00000
00000
00000
11111
00000

and then we flip fourth row, then it'll become all 0s

i could not come up with an O(n^2) greedy solution

my solution is brute force BFS, let this matrix be initial state, we flip row/col and add new matrix to queue, repeat until we see all 0s state, or return false if we have visited all states

Comments (11)